Papers

Betti numbers are central to topological data analysis but fail to capture torsion in integral homology. Torsion can distinguish topological structures with identical Betti numbers, and examples from classical topological data analysis show that it can affect the topology inferred from data. Related torsion-sensitive quantities are also known to have practical applications in graph-based machine learning, including biomedical applications. We investigate how quantum spectral methods can access this additional information. Log pseudodeterminants, obtained by summing the logarithms of the nonzero boundary-Laplacian eigenvalues, summarize spectral information about a simplicial complex. Under explicit topological assumptions, an alternating combination of these quantities gives the size of a higher critical group, the higher-dimensional analogue of a graph sandpile group. With stronger certification, a related construction recovers the size of the torsion subgroup in homology itself. This is, to our knowledge, the first provably correct quantum estimator of integral-homology torsion order. We give a new quantum algorithm for estimating these quantities, with explicit dependence on how the input is queried, the required accuracy, and the spectral gaps. Exact spectra for balanced multipartite clique complexes provide favorable gaps, and a related construction gives an explicit torsion-bearing benchmark. With compact query access, the algorithm need not construct the exponentially large boundary matrices explicitly. For a restricted torsion-bearing family, a tailored amplitude-estimation routine uses quadratically fewer queries than any randomized classical algorithm given comparable access when estimating the log pseudodeterminant. Estimating the full, unnormalized quantity to fixed additive error still costs in proportion to the candidate-space dimension $D$.

Distillable entanglement—the maximum rate of Bell states extractable from the given noisy entangled states via local operations and classical communication (LOCC)—has been a central quantity to characterize the operational value of entangled states. However, this operational meaning had been known to be valid only under a crucial assumption: both parties know the description of the input state and can choose the protocol tailored to it, which does not necessarily reflect the natural operational setting. Here, we show that the distillable entanglement is the fundamental operational quantity even without this assumption. We present a universal LOCC protocol—whose description does not depend on the input state and thus works universally for any input—that achieves the distillable entanglement of an arbitrary unknown input state. Our result therefore lifts the distillable entanglement to a robust notion of an operationally meaningful quantity and clarifies that input-state knowledge is not necessary to achieve the optimal rate of entanglement distillation. Our protocol is based on state merging for compound states, together with the uniform convergence property of the finite-block quantity toward distillable entanglement.

Open quantum systems can rapidly lose most microscopic information, leaving only a few degrees of freedom to govern their long-time dynamics. Classical Markov state models (MSMs) describe such metastable dynamics as transitions among a few representative phases and are widely used to reduce complex-system dynamics in condensed matter and chemical physics. In quantum systems, however, phase labels alone are insufficient when coherence persists between metastable states. Even when the slow modes are known, their spectral projection need not produce valid quantum states. We construct quantum Markov state models (QMSMs) that describe the surviving information and its evolution on a small physical state space containing classical sectors and quantum matrix blocks. We quantify metastability by assuming that the evolution channel $\mathcal C$ changes little when applied a second time, with sufficiently small defect $\eta=\|\mathcal C^2-\mathcal C\|_\diamond$, and that the number of slow degrees of freedom is bounded independently of the full system size. Under these assumptions, we construct compression and reconstruction channels whose composition recovers every reduced state exactly, while the reverse composition gives an exactly idempotent channel approximating $\mathcal C$, answering Kitaev's exact-rounding question [Kit25]. Our constructions give an optimal diamond-norm bound of $\mathcal{O}(\eta^{1/3})$ on all input states, as well as an improved bound of $\mathcal{O}(\eta^{1/2})$ on metastable states prepared by $\mathcal C$, with constants depending only on the slow dimension. The reduced transition channel can be iterated to predict the microscopic dynamics with controlled error. We illustrate the QMSM through a weakly driven dissipative spin chain supporting either a metastable logical qubit or long-lived classical phases.

We develop a submodular framework for the von Neumann entropy of discrete quantum convolutions, providing a noncommutative counterpart to the direct side of entropic additive combinatorics. We first introduce globally weighted quantum convolutions, which form compatible families indexed by admissible subsets of a fixed collection of inputs. Our main theorem reveals a polymatroidal geometry underlying their entropy growth: relative to any fixed admissible input block, the entropy gains admit a normalized, monotone, submodular extension to all subsets of the remaining inputs. The theorem yields convolutional strong subadditivity, quantum Ruzsa triangle inequality, and quantum entropic Plünnecke–Ruzsa inequalities for arbitrary input states. For repeated inputs, it gives sharp comparisons of entropy growth across admissible scales; in particular, the quantum doubling constant controls all higher admissible convolution entropies with optimal exponents. Together, these results bring submodular methods from additive combinatorics into the quantum setting and provide a systematic route to broad families of convolutional entropy inequalities.

Quantum measurements and channels determine how information is extracted, encoded, and transmitted in quantum protocols. Optimizing their performance often requires numerical methods that remain practical as Hilbert space dimensions increase. The Reimpell-Werner iteration offers a practical approach to these tasks through repeated matrix updates that respect the constraints. Here, we generalize this iteration to linear objectives with arbitrary Hermitian cost matrices. We prove that the iterates converge to a global optimum whenever the initialization satisfies suitable support overlap conditions. For each fixed problem, choice of iteration parameters, and admissible initialization, $\mathcal{O}(1/\varepsilon)$ iterations suffice asymptotically to bring the objective value within $\varepsilon$ of the optimum. These results provide a rigorous foundation for the iteration and broaden the class of optimization problems to which its convergence guarantees apply.

Quantum one-time programs (Broadbent, Gutoski and Stebila, CRYPTO 2013) or OTPs for short, enable a functionality to be encoded into a quantum token that can be evaluated on a single chosen input and then becomes unusable. While powerful, this primitive is inherently stateless and tied to a setting in which a quantum token needs to be issued and distributed for every single evaluation of a circuit. This raises a natural question: can the one-time computation paradigm be extended to richer, stateful forms of controlled access, and would such an extension offer inherent advantages beyond standard OTPs? We introduce $\textit{query-limited RAM programs}$ (QLPs), a RAM-generalization of QOTPs that supports structured, stateful computation under bounded or policy-driven access. QLPs allow controlled sequences of evaluations while preventing adversarial forking or rollback of computational state. This enables new applications beyond stateless one-time programs, including quantum tokens for Turing Machines whose size depends only on $\textit{code length}$ (and not runtime), transferable $k$-time or budget-limited programs, and low-communication mechanisms for delegating computation in settings such as Software-as-a-Service. To construct QLPs, we introduce $\textit{one-shot programs}$, unifying one-shot signatures (Amos, Georgiou, Kiayias and Zhandry, STOC 2020) with the single effective query paradigm (Gupte, Liu, Raizes, Roberts and Vaikuntanathan, STOC 2025). We prove that one-shot programs generically imply query-limited programs, demonstrating that the strengthened unclonability guarantees of one-shot signatures translate into enhanced functionality. Along the way, we clarify the relationship between signature-token primitives and quantum one-time programs via generic constructions, essentially showing that one-time signing programs imply one-time general computation.

The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of $n$ copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost $O(2^n)$ per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in $n$ and the inverse additive-error, for input states formed by products of $n$ four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.

We develop a general framework for higher-order quantum resources that treats the resourcefulness of quantum states, channels, and supermaps (also called processes) in a unified manner. By generalizing well-established concepts from resource theories of states and channels, we introduce and study supermap resource monotones and supermap distillation and dilution. As free supermaps, we consider free networks (supermaps that can be implemented with free channels), compatible supermaps (sets of supermaps closed under arbitrary composition), and maximally free superchannels. Specializing to approximate channel-to-channel conversions, we show that under mild assumptions, the conversion error with respect to the diamond distance and the worst-case infidelity coincide. We then apply the general framework to resource theories of dynamical coherence, where we establish the existence of largest sets of compatible supermaps. By characterizing these sets with semidefinite constraints, we show that they are strictly larger than the corresponding free networks but do not contain all maximally free superchannels. We finish by investigating the operational differences of these sets in one-shot channel distillation and dilution, providing solutions for both tasks in the parallel setting and for dilution in the adaptive setting.

Quantum cryptography leverages unclonability to enable a wide range of cryptographic applications that are impossible classically, such as digital currency protected against counterfeiting by quantum mechanics. Security requires that no efficient user can produce even one additional valid banknote beyond those already in their possession. However, existing security bounds weaken as the number of banknotes available to a user increases. In this paper, we study a construction of quantum money whose asymptotic query security does not deteriorate as long as the number of banknotes available to a user remains below the scale required for state tomography. In particular, we show that the construction based on an $n$-qubit Haar-random state and a reflection oracle achieves optimal query security: unless a user holds $\Omega(2^n)$ banknotes, their existing banknotes cannot asymptotically speed up counterfeiting — their best possible attack is the same as if they do not have any banknotes. To establish this result, we develop a framework based on the compressed-oracle technique for defining and analyzing progress measures for quantum tasks such as Haar state cloning. Furthermore, we prove a tight lower bound for generating $r$ additional copies, give a matching attack, and apply our results to quantum copy-protection.

We develop a mixing time method for estimating the sample complexity of quantum state discrimination. We start with considering the minimum-error discrimination of geometrically uniform pure state ensembles, and prove that its sample complexity has a tight estimate given by a quantum homogeneous mixing time [George et al., 2026] and a quantum version of the generalized Dobrushin coefficient [Wolfer, 2020]. This quantum mixing time further reduces to a classical one when the generating group $G$ forms a Gelfand pair with the stabilizer subgroup $H$ of the generator state. In this case the generalized Dobrushin coefficient can be fully expressed by representation-theoretic quantities of the commutative Hecke algebra $\operatorname{End}_G(\mathbb C[G/H])$. In particular, this method reduces the sample complexity estimation of learning quantum coupon collector states [Arunachalam et al., 2020] and learning phase states to classical mixing time problems. We apply this framework to answer the open problems of learning degree-$d$ phase states over $\mathbb F_q$ in [Alrabiah et al., 2026] and generalized Boolean phase states over $\mathbb Z_q$ [Arunachalam et al., 2023]. The framework also applies to hypergraph state ensembles, giving estimates expressed fully in terms of hypergraph data and recovering estimates for graph state ensembles in [Montanaro and Shao, 2022]. Finally, we extend the discussion to arbitrary mixed state ensembles with uniform priors, prove a sandwiched bound for minimum-error discrimination sample complexity by a quantum weakly mixing time, and provide a tight estimate for the minimax discrimination sample complexity from [D'Ariano et al., 2005] by a Dobrushin-type coefficient. We also discuss the method of strengthened data processing inequality [Gao and Rouzé, 2022] and give an upper bound in terms of a strengthened data processing inequality constant.

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $\Omega(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetilde\Omega(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{OV}$), which asks whether an indexed list of $n$ Boolean vectors of dimension $n$ contains two vectors with disjoint supports. In particular, we prove equivalences between $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde \Theta(n^{3/2})$ bound for a variant of $\mathsf{BMPV}$ that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.

The von Neumann, Tsallis, and Rényi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normalization and precision allocation, while variable-time estimation accounts for the probability of reaching expensive spectral tests. With controlled purified access and its inverse, we obtain bounds for additive error $\varepsilon$, rank upper bound $R$, and fixed order $\alpha$. Tsallis entropy estimation has near-optimal rank-independent query complexity $\widetilde O(\varepsilon^{-1/(\alpha-1)})$ for $1<\alpha<2$, when the allowed dimension and rank accommodate the lower-bound instances, and $\widetilde O(1/\varepsilon)$ for $\alpha\ge2$, where $\widetilde O$ suppresses logarithmic factors. The first saves a factor $1/\varepsilon$; the second extends known integer-order scaling to noninteger orders. We also improve the von Neumann entropy bound from $\widetilde O(R/\varepsilon^2)$ to $\widetilde O(R/\varepsilon)$ and obtain $\widetilde O(R/\varepsilon)$ for noninteger Rényi orders $1<\alpha<3$, with further bounds at other orders. Our functional-estimation theorem replaces the global product by a sum of local costs weighted by function magnitudes and spectral masses. We further estimate fixed logarithmic moments and entropy variance using $\widetilde O(R/\varepsilon)$ queries, providing efficient access to fluctuation parameters that enter finite-blocklength quantum compression and pure-state entanglement conversion. More broadly, our framework extends beyond entropy to a broad class of density-matrix functionals, offering a systematic approach toward optimal query complexity in quantum spectral estimation.

Simulating open quantum systems reveals how environmental coupling shapes relaxation, excitation transport, and the dynamics of quantum correlations. On quantum hardware, dissipative channels add operations and might seem to increase cost. However, we show that a broad class of Pauli noise, including depolarization, can ease quantum and classical simulation by exponentially suppressing high-weight components of Heisenberg-evolved observables. For bounded-degree Lindblad dynamics, this permits system-size-independent Trotter steps when estimating local observables. Combining this compression with Richardson extrapolation, we provide classical and quantum error bounds with respect to the 2-norm of the propagated observable. These give high-probability expectation-value guarantees for random input states or random Hamiltonians acting on a fixed state and control (out-of-time-order) correlators. Concretely, we show that expectation values of local observables at time $t$ can be estimated to accuracy $\varepsilon$ using circuits of maximum depth $O\!\left(\left[1+\left(t/\gamma\right)^{3/2}\right]\log^2(1/\varepsilon)\right)$, independent of the system size $n$. Classically, we show that sparse Pauli propagation runs in time polynomial in $n$, $t$ and $1/\varepsilon$ for every fixed $\gamma>0$, with polynomial degree $O(1/\gamma)$ in the weak dissipation limit. The gap between our quantum and classical upper bounds leaves room for a substantial polynomial quantum advantage as dissipation weakens, an observation further supported by our numerical results.

Classical shadow tomography is widely touted as supplying a family of methods for extracting information from quantum systems with polynomially scaling sample-complexities. In the current era of quantum computers possessing on the order of hundreds of qubits, however, polynomial scaling can nonetheless be prohibitive. Thus, there is a strong practical need for obtaining sample-complexity bounds which are as tight as possible. Here we address this in the case of fermionic (matchgate) shadows. For an arbitrary observable $O$ of Majorana degree $2k$, we improve the previously known sample-complexity bound of $\mathcal{O}(n^{2k}\|O\|_\infty^2)$ to $\mathcal{O}(n^{k}\|O\|_\infty^2)$, which is asymptotically tight. For example, for the estimation of the energy per mode of an open fermionic 50-site Hubbard chain with hopping and on site strenghts respectively given by $t=1$, $V=4$, and for a target additive precision of 0.1, this reduces the number of required shots from $\sim 10^9$ to $\sim 10^5$. That is, the new bound reduces the required number of shots by approximately $99.98\%$.

The control of open-system dynamics provides a powerful mechanism for using quantum information to process sequential tasks. While quantum reservoir computing typically relies on Markovian dissipation to process sequential data, the computational role of non-Markovian memory effects remains largely unexplored. We introduce a framework for quantum reservoir computing where non-Markovianity is explicitly modeled and regulated using fractional derivatives. By employing fractional time subordination, we generate tunable, heavy-tailed relaxation dynamics that govern the information backflow between the system and its environment. Non-Markovian information backflow regulates the overall temporal retention of the system, maximizing short-term linear memory capacity. Within an optimal operating regime, fractional non-Markovianity redistributes the reservoir memory towards recent inputs, improving both linear memory capacity and nonlinear prediction accuracy at short delays, at the expense of long-range temporal retention. System-environment interaction proves being not merely a requirement for quantum reservoir computing, but an active resource that embeds memory retention directly into the quantum evolution.

We introduce shadow quantum singular value transformation (Shadow QSVT): given an initial state $|{\psi}\rangle$, a Hermitian matrix $H$, a polynomial $f$, and a set of observables $\{O_1,\dots,O_m\}$, the goal is to estimate $\langle{\psi}|f(H)^{\dagger}O_j f(H)|{\psi}\rangle$ for all $j\in\{1,\dots,m\}$. Shadow QSVT provides a systematic route to reduce the quantum resources required by standard QSVT, which constructs a unitary block-encoding of $f(H)$. It uses structure in the input state and observables, together with the fact that many applications require only observable estimates rather than synthesizing the full unitary. We present three algorithms that exploit structure in the initial state and observables to reduce quantum circuit depth. First, we develop a state-aware QSVT algorithm that prepares the target state with low circuit depth when the Krylov subspace associated with $H$ and $|\psi\rangle$ is low-dimensional or admits an accurate low-dimensional approximation. Second, we introduce an observable-aware Shadow QSVT algorithm that combines a new observable-aware Krylov subspace with history states to further reduce circuit depth and gate complexity. Finally, we develop Classical Shadow QSVT, which constructs a classical representation from $H$, $f$, and $|\psi\rangle$ without prior knowledge of the observables or explicit preparation of the target state proportional to $f(H)|\psi\rangle$. This representation enables estimation of the target quantities for observables specified after the quantum computation. Together, these three algorithms provide tools for reducing the circuit depth of QSVT-based computations across a range of settings.

We determine which representation sectors control the slowest convergence of random Pauli rotations and several local random quantum circuits. For $d=2^n$, the continuous Pauli walk has exact all-representation gaps $$\Delta_{\mathsf{SU}(d)}=\frac{d-8}{8(d-1)}\quad(n\ge4),\qquad \Delta_{\mathsf{PU}(d)}=\frac{d(d-3)}{8(d^2-1)}\quad(n\ge3).$$ The special-unitary gap is attained in $\bigwedge^8\mathbb{C}^d$ and is invisible to balanced moments, while the projective gap is already attained in a balanced fourth-moment representation. We obtain exact discrete and orthogonal Pauli analogues, exact finite-Clifford chain/path gaps, and dimension-independent all-representation Haar brickwork lower bounds; on three qubits every weighted Haar-$\mathsf{SU}(4)$ edge walk reduces to one universal principal-angle constant. For real complete-graph models, the entire ordinary fourth-tensor gap reduces to a quadratic-size occupation operator, is simple for every $n\ge4$, and has an expansion beginning $$\Delta_n^{(4)}=\frac{10}{9n}-\frac{88}{105n^2}+O(n^{-3}),$$ with competing branches separated only beyond all algebraic orders. For the two finite real Clifford complete-graph walks, this fourth-tensor mode is the exact all-representation group gap for every $n\ge144$; in the same range it simultaneously governs every ordinary even tensor degree $k\ge4$. Thus different representation scopes can have genuinely different slow modes.

We study both the classical and the quantum complexity of the problem of estimating disorder-averaged quench dynamics for all-to-all spin Hamiltonians such as quantum Hopfield, Sherrington–Kirkpatrick (SK) or Dicke-type models. Disorder averaging restores permutation invariance in this setting, so states of $N$ spins can be stored in $\mathcal O(\log N)$ qubits. While logarithmic-space quantum computations are known to be simulatable classically in polynomial time or in polylogarithmic space, whether a single algorithm can achieve both is open, raising the possibility of simultaneous quantum advantage. To this end, we give a quantum algorithm for permutation-invariant $k$-local dynamics without disorder using polynomial time and $\mathcal O(\log N)$ quantum and classical space. We show that any classical algorithm matching these resources would imply $\mathsf{BQL}\subseteq \mathsf{SC}$. For short times, however, we provide such algorithms, including for SK models. For Hopfield models, we discuss how dilating the disorder to ancilla qubits reduces the problem to the disorder-free case on an enlarged system, thus extending both classical and quantum results to them. We give some evidence that their long-time dynamics are non-trivial. They thus emerge as a candidate for a simultaneous time–space advantage in quantum simulation.

We introduce the quantum Černý complexity $\mathrm{qc}(w)$ of a binary word $w$: the least dimension $d$ for which there exist quantum channels $A_0,A_1$ on $d\times d$ density matrices and a start state $\rho_0$ such that $w$ is the unique shortest word whose associated channel is constant on the reachable set. We show that $2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ for every nonempty $w$, a quadratic saving over the classical analogue, and that constant words are extremal: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. In contrast, $\mathrm{qc}(01^n0)=2$ for every $n\ge 1$, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and $\mathrm{qc}$ is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant $\mathrm{qcp}$ in which the synchronization target is required to be a pure state. We prove that in dimension $2$ no word of length at least $2$ can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving $\mathrm{qcp}(01^n0)=3$ with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that $\mathrm{qc}$ is computable, by reduction to the first-order theory of the reals.

As LLMs grow in size, compression becomes increasingly important for efficient deployment. SVD-based low-rank compression reduces parameter counts but can degrade downstream performance. To improve performance after compression, we introduce QuLoC, a photonic quantum-assisted LLM compression algorithm that uses quantum circuit outputs to gate the retained low-rank components during training. Model performance is recovered through local functional reconstruction followed by end-to-end knowledge distillation. After training, the gating coefficients are absorbed into the low-rank factors, allowing the compressed model to run on classical hardware without executing quantum circuits during inference. Experiments on Qwen3.5-4B show that QuLoC achieves a 9.73% relative improvement in average accuracy over state-of-the-art baselines across multiple downstream tasks, demonstrating its effectiveness. We further evaluate QuLoC on LLaMA-7B at different parameter compression ratios. It achieves comparable or higher average downstream accuracy than state-of-the-art baselines, supporting its applicability to a larger model across different compression settings. These results motivate further exploration of photonic quantum-assisted compression for larger models and more complex agentic tasks.

Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in a known state. In this work we study catalytic implementations, i.e. asking whether dirty qubits can instead be used provided that their joint state including any entanglement with other registers is restored exactly at the end of the computation. We show that every $n$-qubit Clifford circuit has a catalytic implementation of depth $O(\log n)$ using $O(n^2/\log^2 n)$ catalytic qubits and no clean qubits, matching the asymptotic depth achievable when clean workspace is available. We extend this approach to diagonal elements of any fixed level $C_k$ of the Clifford hierarchy, which admit catalytic implementations of depth $O(\log(n+1))$ with $O(n^k/\log(n))$ gates and $O(n^k/\log^2(n))$ catalytic qubits, as well as to semi-Clifford Gates.

We present Smite, a Python toolkit for quasiclassical trajectory (QCT) simulations of reactive and inelastic bimolecular collisions, unimolecular dynamics, and molecular collisions with finite surface models. A central feature is the explicit control of reactant preparation: harmonic normal modes admit fixed quantum numbers, prescribed energies, thermal quantum populations, or ground-state Wigner sampling; rotation is prepared at fixed angular-momentum magnitude or from thermal distributions appropriate to diatomic and polyatomic rotors. Rotating-Morse sampling provides a coupled anharmonic treatment of diatomic vibration and rotation, while saved molecular-dynamics phase points provide an alternative source of initial conditions. The same nuclear propagators operate with on-the-fly electronic-structure calculations or user-supplied analytical and machine-learned potential energy surfaces. Additional modules provide constrained rigid-fragment dynamics, thermostat-based preparation, photoionization initial conditions with energy and recoil constraints, and fewest-switches surface hopping (FSSH) on multiple PESs with approximate curvature-derived couplings. Geometry optimization, transition-state searches, crossing-point optimization, intrinsic-reaction-coordinate following, and thermochemistry use the same energy and derivative interfaces. Analysis tools connect trajectories to product energy partitioning, stereodynamical correlations, time-resolved vibrational signatures, and independent-atom x-ray scattering.

The iterative quantum phase estimation algorithm (IPEA) is better suited for NISQ and early fault-tolerant hardware compared to the original algorithm, which requires the inverse quantum Fourier transform. However, current error mitigation and correction implementations lead to imperfect unitaries, causing erroneous phase feedback in IPEA. To improve the reliability of phase bits is to repeat the k^th iteration for the 2^k-th power of the unitary $N_k^*$ times, followed by a majority decision. However, due to variations in their circuit complexities, different iterations incur varying resource costs ($w_k$) and different per-shot error probabilities ($q_k$). Given tight resource constraints, we ask what the optimal number $\{N_k^*: 1\le k \le L\}$ of shots per bit is: $$\arg \max_{\{N_k\}} \mathbb{P}(\text{all } L \text{ bits correct}) \text{ s.t.} \sum_{k=1}^L w_k N_k \le W$$ We obtain closed-form expressions for $N^*_k$ under the conditions: $W \gg \sum_k w_k $(enough for at least one shot per iteration), $w_k$ increases with $k$, $q_k$ are small enough and $L$ is large. We do so by analyzing tractable upper and lower surrogate problems derived via tight concentration and anti-concentration bounds and showing that their solutions converge when $q_k\ll 1$. We observe that when $W\gg \sum_k w_k \ln\! \left(\sum_k w_k\right)$, the optimal $N_k^*$ is proportional to $\frac{\ln\! \left(\sum_k w_k\right)}{c_k}$ and does not depend on individual $w_k$, where $c_k=-\ln\left(2\sqrt{\left(1-\frac{q_k}{2} \right) \frac{q_k}{2}}\right) \propto \ln\frac{1}{q_k}$. However, when $\sum_k w_k \ll W\ll\sum_k w_k \ln\! \left(\sum_k w_k\right)$, the allocation is also (additively) influenced by $\frac{1}{c_k}\ln\frac{1}{w_k}$ for larger values of $k$, i.e., higher powers of unitary. These results lead to simple rules of thumb for resource allocation that may benefit the design of practical systems.

We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneous coordinate permutations, we prove $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$ denotes public-coin randomized communication complexity, and $Q^{\ast}$ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed $\varepsilon\in(0,1)$, there are binary permutation-invariant partial functions with quantum communication complexity $O_\varepsilon(\log\log n)$ and randomized communication complexity $\Omega_\varepsilon((\log n)^{1-\varepsilon})$. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed $\varepsilon\in(0,1)$, we exhibit permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum communication complexity $O_\varepsilon(\log n)$ and randomized communication complexity $\Omega_\varepsilon(n^{1-\varepsilon})$. For graph-invariant partial functions on $v$-vertex graphs, we obtain $O_\varepsilon(\log v)$ quantum versus $\Omega_\varepsilon(v^{2-\varepsilon})$ randomized communication complexity. All separation protocols require no prior entanglement.

Directly solving the full electron-nuclear Schrödinger equation remains one of the grand challenges in quantum mechanics. Here, we propose a quantum-chemically motivated orbital-based neural network wavefunction ansatz with explicit many-body electron-electron correlation terms, with parameters depending on the entire electron-nuclear configuration, enabling an accurate description of strongly correlated and/or multi-reference electronic structures by a single Slater-determinant across a broad nuclear configuration space. To train this wavefunction, we further develop an efficient hybrid optimization strategy that combines the variational Monte Carlo technique with local-energy constraints, mitigating the intrinsic sampling bias of the former and considerably reducing the statistical error. These advances are embedded in a unified neural network framework, Schrödinger, enabling the determination of globally accurate potential energy surfaces with a single training for systems ranging from strongly correlated diatomic molecules, triatomic reactions containing conical intersections, to polyatomic multi-reference molecules. This work offers a practical machine-learning tool for solving the electron-nuclear Schrödinger equation and capturing full quantum effects beyond the Born-Oppenheimer approximation.

Classical shadows are an influential framework for compressing copies of a given quantum state $\rho$ into classical data $S$, enabling many properties of $\rho$ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given $S$, when can one efficiently verify that $S$ came from a genuine $n$-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given $S$ that allows one to capture 2-local properties of $\rho$, can one fake or spoof a shadow $S'$ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all $n$-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-$\Sigma_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$\Sigma_2$ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals $S$ of a quantum state $\rho$, estimating the 3-local marginals of $\rho$ is intractable unless QCMA $\subseteq$ BPP, even if the state $\rho$ is the unique state consistent with $S$.

We present a complete set of $16$ rewrite rules for multi-qudit Clifford circuits in all odd prime dimensions. Completeness means that any two Clifford circuits representing the same linear map can be rewritten into each other using these rules. Each rule involves at most three qudits and admits an intuitive interpretation. To establish completeness, we first work at the symplectic level, using the isomorphism between the symplectic group $\mathrm{Sp}(2n,\mathbb{Z}_p)$ and the quotient of the Clifford group by the Pauli group. We construct a circuit normal form that captures the stabiliser tableau of a Clifford operator and is unique up to Pauli correction. Using this normal form, we derive a complete set of symplectic relations, which we then lift to Clifford relations by incorporating Pauli corrections. We also formally verify completeness in the Agda proof assistant.

Quantum algorithms can offer substantial computational speed-ups, yet these advantages may disappear once the cost of structure-agnostic classical data encoding is taken into account. Real-world problem instances, however, often possess rich internal structure. This raises a fundamental question: can such structure be harnessed to make quantum speed-ups survive end-to-end cost accounting? Here we show that it can. We introduce a general framework for structure-aware quantum data encoding that compiles compact recursive descriptions of problem structure into efficient state-preparation circuits, translating structural information directly into reduced encoding complexity. For the uncapacitated facility-location problem, structure-agnostic encoding admits a classical dequantization that eliminates the quadratic quantum speed-up, whereas exploiting the underlying problem structure restores this advantage even when state-preparation costs are included. More broadly, the same framework prepares structured quantum states for combinatorial optimization that capture non-trivial relations among constraints, including group balance, conflicts and synergistic rewards, extending previously reported super-polynomial quantum advantages to broader classes of objectives. These results establish exploitable problem structure as a computational resource for quantum algorithms and provide a systematic route towards realizing quantum advantage in data-intensive problems.

Sampling problems give some of the clearest conditional separations between quantum and classical computation. In Fermion Sampling, passive linear optics acts on a non-Gaussian magic input. Globally Haar-random transformations give anticoncentration and high-precision average-case hardness, but require linear depth and quadratically many gates. A natural open question is whether linear depth is necessary? We show that logarithmic depth suffices for both guarantees in the same ensemble. For fresh uniform matchings with independent Haar two-mode gates, the collision reaches the passive-Haar scale at a sharp threshold of $\log n/\log(9/4)\approx0.855\log_2 n$ layers, with an explicit limiting transition profile and a matching lower bound from two-particle correlations. The mechanism is input-dependent: the magic input suppresses the extensive weight of the slowest relaxation mode, leaving the next to set the scale. An occupation-basis input retains large collision even under full Haar randomness. At a larger logarithmic depth, we prove, in the real-RAM model, average-case $\#\mathsf{P}$-hardness of estimating output probabilities to additive error $2^{-O(n\log^2 n)}$ on any fixed fraction of instances above $3/4$. We construct hard instances in four native layers, embed them in typical schedules, and interpolate along Cayley paths using a rational linear-program decoder. A finite $192$-gate alphabet preserves the collision law exactly. Both guarantees use logarithmic native fermionic depth between arbitrary mode pairs and $O(n\log n)$ gates, replacing the global-Haar construction's quadratic budget. The accuracy proved is finer than the $1/N$ scale, where $N=\binom{n}{n/2}$, required by sampling-to-counting; hardness of sampling within constant total-variation distance remains open.

The one-way model of measurement-based quantum computing implements computations via successive adaptive single-qubit measurements on a resource graph state. This model has practical applications, particularly in photonics, and it is also useful as a theoretical tool e.g. for optimisation. Gflow is a necessary and sufficient condition for implementing certain one-way computations deterministically (in a suitable sense); it is also used in efficient translations from the one-way model to quantum circuits. For a computation on $n$ qubits, a gflow can be found in $\mathcal{O}(n^3)$ time. Here, we consider an incompletely specified computation given by an unlabelled open graph: the graph state as well as the input and output qubits are known, but the measurements have not yet been fixed. We give an algorithm that identifies a measurement labelling and a compatible gflow, and runs in $\mathcal{O}(n^3)$, strictly generalising the previous approach. The new algorithm can also handle restrictions on the order of the measurements and returns only solutions compatible with these constraints. We additionally prove that if an open graph has equal numbers of inputs and outputs, it has at most one labelling compatible with gflow; and show how to identify additional inputs for an open graph that does not yet have the maximal number, without breaking an existing gflow.