Papers

Secret sharing is ubiquitous throughout cryptography. All possible access structures are classically feasible, and in the case of threshold access structures, the protocols are even very efficient. However, when moving to the quantum setting, the no-cloning theorem shows that many access structures are impossible. In fact, no-cloning exactly characterizes feasibility: for thresholds, quantum secret sharing is possible if and only if the threshold $t$ is strictly more than $n/2$. In this work, we propose a variant of quantum secret sharing (QSS) where two or more identical copies of the input state are provided, but the output is only required to recover one copy. This notion circumvents the simple one-copy no-cloning obstruction, though the natural $k$-copy generalization still gives much milder obstructions. For thresholds using $k$ copies, no-cloning implies that QSS is impossible whenever $t\leq n/(k+1)$. It is tempting to hypothesize that no-cloning continues to exactly characterize the many-copy case. However, we show that this is not the case. We give positive results showing that multiple copies allow for going slightly beyond the single-copy obstruction: for thresholds, we construct QSS whenever $t>(n-k+1)/2$. On the other hand, we give a novel obstruction we call the Clique Path obstruction, which applies to arbitrary access structures. For thresholds, it shows that QSS is impossible whenever $t\leq (n-1)/k$. Our upper and lower bounds exactly match for $k=2$. Both our results leverage connections to the $k$-colorability of certain graphs derived from the access structure. We leave closing the gap for $k\geq 3$ copies as a fascinating direction for future work. Secret sharing is closely related to error correction, which can also be considered in the many-copy setting. Our results imply similar obstructions for quantum error correction for erasure channels.

We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension $d$, an erasure probability $p$, a blocklength $n$, and $M$ equiprobable messages, the optimal success probability is equal to $E[\min\{1,d^K/M\}]$, where $K$ is binomial with parameters $n$ and $1-p$. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-$d$ digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer $M$. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.

Macrorealism is a fundamental concept in quantum foundations, capturing basic features of our everyday experience. Among the main tools introduced to test violations of macrorealism are the Leggett-Garg inequalities. These inequalities provide necessary and sufficient conditions for a certain data set including the correlators measured in a number of different experimental runs (weak version of macrorealism). Leggett-Garg inequalities have proved useful for detecting violations of macrorealism in neutrino oscillation experiments. However, it is interesting to investigate a set of necessary and sufficient conditions for strong macrorealism - no-signaling-in-time and arrow-of-time conditions - in order to obtain a more complete characterization of macrorealism in the context of neutrino oscillations. In particular, here we extend previous study of the no-signaling-in-time condition to the case of three-flavor neutrino oscillations, including the CP-violating phase of the Pontecorvo-Maki-Nakagawa-Sakata matrix.

A hidden-variable model can reproduce context-independent individual readouts while failing to preserve observable records when devices are connected or reused. We distinguish two composition requirements. For a finite family of nonnegative instrument matrices, an invariant space generated by normalization defects characterizes unit continuation mass under every finite adaptive policy. Its annihilator defines the maximal admissible positive cone closed under outcome-conditioned updates. A separate observation space characterizes indistinguishability of context-dependent hidden preparations under joint readout. A finite-state example passes every fixed sequence but fails under outcome-dependent stopping. For a wrapped-Cauchy spin source with an explicitly stipulated unchanged-source passive extension, two individually fair probes acquire a setting-dependent agreement probability with contrast $\epsilon^2\operatorname{sech}(2g)/4$. More generally, protection under one and two identical uses forces a continuous binary passive response to be constant; measurable two-valued exceptions remain possible. Exact rational calculations, exhaustive finite-policy experiments, continuous source sampling, and quadrature test the stated examples. The criteria apply to specified instrument families and accessible records; they do not construct a microscopic detector or establish consistency under unrestricted network composition.

Given multiple uses of an unknown quantum channel, we determine whether it is a specified non-mixed-unitary channel or belongs to the set of mixed-unitary channels. Formulating this as a composite channel hypothesis testing problem, we characterize the Stein exponents achievable by parallel strategies under progressively weaker restrictions on probe states and auxiliary memory. In particular, we consider block-i.i.d. probes, which allow arbitrary correlations within blocks of fixed size while remaining i.i.d. across different blocks, and derive finite-letter expressions of the corresponding Stein exponents. Varying the block size, which interpolates between fully i.i.d. and arbitrary probes, together with further restrictions on intra-block correlations and access to auxiliary memory, results in a multifaceted hierarchy. We establish several strict separations within this hierarchy. Without auxiliary memory, we prove that fully i.i.d. probes yield a vanishing Stein exponent for every unital non-mixed-unitary channel, while blocks of three product probes suffice to obtain a strictly positive exponent for the qutrit Werner-Holevo channel. For block size two, although product probes seem to be insufficient for $O(3)$-covariant channels, an entangled probe achieves a strictly positive exponent for the qutrit Werner-Holevo channel, even though every maximally entangled probe fails. In contrast, access to auxiliary memory makes fully i.i.d. probes sufficient by yielding a strictly positive exponent for every non-mixed-unitary channel, even without requiring input-reference entanglement, and this exponent admits a lower bound determined by the diamond-norm distance from the mixed-unitary set. Moreover, for odd-dimensional Werner-Holevo channels, we find that this exponent is infinite, with every full-Schmidt-rank pure state being optimal.

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth $\mathsf{poly}(n)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in $n$, which is the best possible, and an exponential improvement on the previous best bound of $2^{n/2}$ due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.

Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.

A majority of measurable dynamic quantities of a physical system is described as an equilibrium correlation function of the form $G_{AB}(t-t') = \left<A(t)B(t')\right>$, where $t'$ represents the impact time and $t$ represents the response time. Conventional quantum algorithms to compute such quantities via Hamiltonian simulation such as the Hadamard test, variational methods, or linear-response-based algorithms share one feature in common: each time point $t-t'$ is calculated by a different quantum circuit, leading to at least $O(N_t)$ total shots, and at least $O(N_t^2)$ total quantum gates. Here, we provide a different approach: utilizing $O(\log N_t)$ ancilla qubits to store time as a quantum variable, and effectively parallelize the computation of an equilibrium correlation function by requiring only a single quantum circuit for all time points. We show that this circuit needs to be run only $O(\log N_t)$ times, which in total requires $O(N_t \log N_t)$ quantum resources in the large system size limits. We prove that this scaling is optimal, and demonstrate our algorithm calculating the Green's function of a one-dimensional spinless Hubbard model.

Multiterminal Josephson junctions, in which one weak link couples three or more superconductors, are studied as hosts of topological Andreev bands, multi-pair supercurrents and tunable circuit elements. Their currents are modeled both as pairwise networks of two-terminal couplings and through genuinely multiterminal processes such as quartets. We ask how accurate the pairwise description is and what controls its error. In a microscopic scattering model of planar junctions, we compare exact currents with the best pairwise approximation, which allows arbitrary nonsinusoidal couplings. In ensembles of disordered three- and four-terminal junctions, the pairwise terms capture nearly all of the energy variation, yet the median current error ranges from 8.0 to 21.2 percent, about twice the energy error, because currents weigh the multiterminal harmonics more strongly. Designed devices extend the comparison to sixteen terminals. We identify a mechanism that controls this error. A normal-region mode near the Fermi level that couples to three or more terminals produces large nonpairwise currents, and detuning it with a gate suppresses them. Shifting only this mode, selected from normal-state properties, predicts the gate dependence of the error in eight three- and four-terminal devices without fitting currents. Finite-gap calculations in two clean devices confirm a drop from tens of percent near resonance to below one percent. An analytic single-level model gives a sufficient detuning for pairwise accuracy at any terminal count. Planar junctions thus inherit the resonant and cotunneling regimes known from quantum dots, and normal-state properties identify the mode that selects between them.

We apply Decoded Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising spin Hamiltonians. We show that this Gibbs sampling problem reduces to a quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $\beta_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many algorithms, including Glauber dynamics and any algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical algorithm based on Prange's method, and by DQI equipped with a quantum decoder. For example, when $D=\alpha k$ with fixed $\alpha>1$, both Prange's algorithm and DQI can sample at any inverse temperature $\beta < \tanh^{-1}(1/\alpha)$ for sufficiently large $k$, well beyond the dynamical threshold $\beta_{\rm dyn} \sim \sqrt{2\ln k / (\alpha k)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable algorithms.

Standard finite quantum de Finetti theorems approximate the $k$-system marginals of permutation-invariant states of $n$-systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our $k/n$ error bound in max-relative entropy improves on the previously best known $k^2/n$ scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels $N^{(n)}:A^{\otimes n}\to B^{\otimes n}$, where $d_A=\dim A$, we prove that the $k$-system reduced channel is CP-dominated by a mixture of tensor-power channels with error $O(k/\sqrt{n})$ and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of $r$ defects, the representation error is at most $\mathrm{poly}(n)\bigl(2d_A^4k^3/(nr^2)\bigr)^{(r+1)/2}$ and decays exponentially in $n$ for a suitable choice of parameters $r$ and $k$.

We study multi-armed bandits whose arms supply unknown quantum states and whose mean rewards are defined by a known effect $F$. Each fresh copy may be measured by an arbitrary, adaptively chosen POVM. We prove an exact collapse: the measured relative entropy from an arm state to its confusing reward half-space equals the classical Burnetas-Katehakis functional of $F$'s spectral statistics, and the spectral measurement of $F$ together with an explicit least-favorable state, built from the derivative of the matrix logarithm, forms a saddle point of the underlying measurement game. Consequently, spectral measurement followed by classical KL-UCB is asymptotically instance-optimal among all consistent single-copy policies, in every finite dimension and for every reward effect under the stated nondegeneracy assumptions: adaptive and randomized measurement design cannot improve the leading logarithmic regret coefficient, and neither can storing copies for later single-copy measurement. A self-contained finite-time bound covers general effects and boundary distributions. Any further improvement must come from measurements outside the single-copy class. For consistent policies with arbitrary quantum memory, an amortized relative-entropy argument gives a converse with the Umegaki half-space divergence, and the two per-arm regret floors, $1/K_{\mathrm{inf}}$ and $1/D_{\mathrm{inf}}$, coincide if and only if the arm commutes with $F$. Whether the Umegaki floor is attainable involves a composite quantum Stein problem and a separate reduction to adaptive regret; we pose it as an open problem, with two-copy numerical evidence.

Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy—based on local consistency of pairwise reduced density matrices—is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/\epsilon^2)$ and $\mathcal{O}(n/\epsilon)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $\epsilon$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm—a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $\Omega(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $\Omega(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

Quantum data hiding concerns pairs of states which are highly distinguishable with global measurements, yet nearly indistinguishable when restricted to local operations and classical communication. More than two decades after Eggeling and Werner introduced a multipartite hiding scheme based on Werner states, the optimal dependence of its uniform security guarantee on the number of parties and local dimension remained unknown. We resolve this problem by showing that the distinguishing bias of any pair of $n$-qudit Werner states is $O(n^2/d)$ under measurements whose effects remain positive under partial transposition (PPT) across every bipartition. An explicit pair attains this scaling using only nonadaptive local measurements, establishing worst-case optimality and showing that the PPT relaxation preserves the optimal dependence on both the number of parties and the local dimension. At fixed security, this extends the certified hiding regime from $n=O(d^{1/4})$ to $n=O(\sqrt d)$. Beyond data hiding, the same bound implies that testing any nontrivial unitarily invariant property with adaptive single-copy measurements requires $\Omega(\sqrt d)$ copies, yielding separations for any property with dimension-independent sample complexity under collective measurements. Our proof reduces the distinguishing bias to trace norms of partially transposed operators and analyzes them using mixed Schur-Weyl duality, demonstrating the utility of representation theoretic methods developed for port-based teleportation to data hiding and quantum property testing.

Linear threshold functions are $f_{w,\theta}(x)=\text{sign}(\langle x,w \rangle -\theta)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $\theta\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$. When $\theta=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute $f_{w,\theta}(x)$ at any $x\in\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,\theta}$ up to Euclidean error $\epsilon$ using $O(\log(n/\epsilon))$ membership queries and $\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,\theta}$ up to error $O(\epsilon)$ when $x$ is Gaussian. Classical algorithms need $\Omega(n\log(1/\epsilon))$ queries. 2. A homogeneous LTF $f_w$ on domain $\{-1,1\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries. We give an exponential improvement, using $O(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) quantum examples under Gaussian measure, corresponding to $\int_x \sqrt{\gamma_n(x)}|x\rangle |f_w(x)\rangle dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs $f_w$ with error $\epsilon$ under the Gaussian distribution, using $O(n^{1/4}/\sqrt{\epsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/\epsilon^4)$ other gates.

Cooling an arbitrary mixed state to a pure ground state requires transferring its entropy to an environment. Can a single coherent bath contact accomplish this without repeated bath resets? We develop a new cooling mechanism that transfers the input information into bath degrees of freedom that subsequently decouple, while the system and the remaining bath follow a ground-state path. The bath is discarded only at the end, and the system Hamiltonian remains on and unmodified throughout. We rigorously realize this mechanism for a class of weakly interacting, gapped fermionic systems with local interactions. Starting from any mixed state, our protocol prepares the interacting ground state in total physical time polylogarithmic in the system size and inverse global trace-norm error. It uses two initially empty bath modes per system mode and a single pulse shared across all onsite system–bath couplings. The same pulse prepares each admissible system's own ground state without knowledge of its microscopic parameters. The guarantees follow directly from a non-Markovian system–bath dynamics without an effective Lindbladian description.

Modern smart grids generate increasingly rich operational data and deploy greater numbers of remotely controlled switching assets than ever before, creating new opportunities for data-driven distribution network reconfiguration (DNR). DNR optimizes grid topology to improve efficiency, reduce power losses, and maintain operational constraints, but finding optimal switch configurations remains a computationally demanding combinatorial problem. In this paper, we propose a deep reinforcement learning (DRL) framework for static DNR to systematically investigate how the Q-network architecture affects both solution quality and learning performance. We evaluate multiple architectures within a controlled DRL framework, varying only the Q-network to isolate the contribution of each architectural choice. Our results show that quantum-enhanced Q-networks can achieve higher rewards with fewer parameters than their classical counterpart, suggesting that such architectures are a promising direction for combinatorial power systems optimization.

We prove maximal separations: $n$-qubit systems can have $\Theta(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation—computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $\lambda$ catalysts; but (ii) cannot be solved by any algorithm with $c\lambda$ catalysts, for any $c<1$. We show this by proving query lower bounds for quantum-space bounded algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful—there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full $\Theta(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy—analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.

We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when $m\approx n^2/2$, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires $m \approx n^2/3$ vectors, thus removing the hope for an exponential quantum advantage in this parameter regime. Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed $\epsilon>0$, our quantum algorithm solves $\mathbb{F}_3$-subset sum in polynomial time with $m=\epsilon\cdot n^2$ vectors. More generally, we establish a full sample–time tradeoff that interpolates between exponential and polynomial runtime. The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample–time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).

Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS) quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla qubit participates in at most one two-qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the quantum parity constraints equals the minimum two-qubit depth when each stabilizer check is measured with a single ancilla. We introduce local automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph automorphisms and lifts each feasible orbit assignment to the full graph. Although the $6$-layer degree lower bound is unattainable for the published weight-$6$ IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full automorphism group of the Tanner graph, we construct translation subgroups for two-block group-algebra CSS codes over abelian groups. For quantum Tanner codes, we give conditions under which square-complex symmetries extend to Tanner graph automorphisms.

We present a quantum algorithm that generates a uniform superposition over the spanning trees of a graph – also known as a q-sample – using only a sub-linear number of queries to the graph. This goes beyond previous work that focuses on generating classical samples, including a recent quantum algorithm by Apers, Gao, Ji, and Liu [ICALP 2025]. For an $n$-vertex, $m$-edge graph, our algorithm admits a pre-processing step of $\tilde{O}(\sqrt{mn} + m^{1-\delta})$, after which each q-sample can be generated in $\tilde{O}(n^{1+2\delta})$ for any $\delta$. Alternatively, $k$ independent q-samples can be generated at a total cost of $\tilde{O}(\sqrt{kmn})$. We also prove a matching lower bound up to logarithmic factors, showing that our algorithm is essentially optimal. Further tradeoffs are given in the paper. In comparison, the optimal classical algorithms (Anari, Liu and Vuong [FOCS 2022]) need an $\tilde{O}(m)$ pre-processing step, after which each sample costs $\tilde{O}(n)$ operations. These results yield faster quantum walk-based algorithms for counting spanning trees or finding a marked one. Our result is obtained via quantum walk sampling over a sequence of slowly-changing Markov chains. Each chain is an isotropized up-down walk that mixes rapidly to the spanning tree distribution of the input graph. A key ingredient is an amortized data structure supporting fast implementation of the associated quantum walk operators throughout the sequence. This data structure maintains access to a spectral sparsifier and a leverage score sampler that evolve with the underlying graph.

In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.

Mutually unbiased bases (MUBs) describe quantum measurements for which certainty in one basis gives uniform outcomes in the others. Their maximum number remains unknown in dimensions that are not powers of a prime. We introduce an ansatz that, in many dimensions, allows us to construct more MUBs than have previously been found. Each basis in the ansatz consists of a diagonal phase matrix applied to a fixed unitary, which is a tensor product of Fourier matrices and, optionally, any real Hadamard matrix. This construction yields five MUBs in dimension 12, six in dimensions 48, 96, and 192, seven in dimensions 36 and 108, and ten in dimension 648. These bases can then be extended to exceed the tensor product bound, asymptotically, in every eighteenth dimension. Moreover, we show that Paley's real Hadamard matrix can be used to construct $q+1$ bases in dimension $d = q(q+1)$ for every prime power $q\equiv3\pmod4$. This count grows as $\sqrt d$ and cannot be exceeded by tensor products of smaller sets.

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $\Omega(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.

The Quantum Approximate Optimization Algorithm (QAOA) is regarded as a promising candidate for near-term quantum advantage in combinatorial optimization, yet our ability to study it at scale is limited. Exact recursive formulas have been introduced for predicting QAOA performance on large spin glasses, but the computational cost of evaluating them grows exponentially with the number of QAOA layers, preventing the study of QAOA in the promising high-depth regime. In this work, we show that for the task of computing QAOA energy on any mixed dense spin glass problem, spins approximately decouple into independent spin-boson systems. In the infinite-size limit, the decoupling becomes exact, establishing the spin-boson mapping as a natural framework for the many-body physics of QAOA. This generalized spin-boson mapping gives a recursive procedure for computing QAOA energies that can be executed at modest cost using tensor networks. As a numerical application, we optimize QAOA on pure and mixed spin glasses at depths intractable for prior techniques, observing that higher-degree problems require more layers for a comparable approximation ratio while angle optimization becomes more challenging. While decoupling enables the evaluations of QAOA energies at large size and depth, it does not enable strong simulation of QAOA; a quantum computer is required to sample the bitstring corresponding to the predicted energy.

A central yet mysterious problem in quantum information is the asymptotic distinguishability of quantum states under restricted measurements. Here we look at asymptotic asymmetric hypothesis testing for general multi-mode bosonic Gaussian states restricted to arbitrary collective Gaussian measurements. We establish a single-letter formula for the Stein exponent for many pairs of states, featuring two distinct contributions, corresponding to first and second moments, respectively. Remarkably, the Gaussian-measured relative entropy exhibits genuine non-additivity, but the only effect of additivity violations is to asymptotically decouple first and second moments. We prove this by establishing sufficient conditions for additivity of the second-moment term via novel log-determinant matrix inequalities. Our results not only identify a single-letter expression for the Gaussian Stein exponent in a wide range of practical situations, but also rule out any possible advantage from collective Gaussian measurements when considering centred Gaussian states.

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $\gamma:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $\gamma^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(ns\gamma^{4.5}+ms\gamma^2\right)$. For $\gamma=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses classical-accessible random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to any classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs. We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.