Search

The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Even with NLTS now solved, there remain many independent and unresolved prerequisites to the QPCP Conjecture, such as the NLSS Conjecture of [GL22]. In this work we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose low-energy states all require $\omega(\log n)$ T gates to prepare. In fact, we prove a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require $\Omega(n)$ T gates. We further show that our procedure can be applied to the NLTS Hamiltonians of [ABN22] to yield local Hamiltonians whose low-energy states require both $\Omega(\log n)$-depth and $\Omega(n)$ T gates to prepare. In order to accomplish this we define a "pseudo-stabilizer" property of a state with respect to each local Hamiltonian term, and prove an additive local energy lower bound for each term at which the state is pseudo-stabilizer. By proving a relationship between the number of T gates preparing a state and the number of terms at which the state is pseudo-stabilizer, we are able to give a constant energy lower bound which applies to any state with T-count less than $c \cdot n$ for some fixed positive constant $c$. This result represents a significant improvement over [CCNN23] where we used a different technique to give an energy bound which only distinguishes between stabilizer states and states which require a non-zero number of T gates., Comment: fixed typos, updated abstract, additional references added

The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.

The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation., Comment: 49 pages, 9 figures

We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle: (a) $\mathsf{BPP}^{\mathsf{QNC}^{\mathsf{BPP}}} \neq \mathsf{BQP}$. This refutes Jozsa's conjecture [QIP 05] in the random oracle model. As a result, this gives the first instantiatable separation between the classes by replacing the oracle with a cryptographic hash function, yielding a resolution to one of Aaronson's ten semi-grand challenges in quantum computing. (b) $\mathsf{BPP}^{\mathsf{QNC}} \nsubseteq \mathsf{QNC}^{\mathsf{BPP}}$ and $\mathsf{QNC}^{\mathsf{BPP}} \nsubseteq \mathsf{BPP}^{\mathsf{QNC}}$. This shows that there is a subtle interplay between classical computation and shallow quantum computation. In fact, for the second separation, we establish that, for some problems, the ability to perform adaptive measurements in a single shallow quantum circuit, is more useful than the ability to perform polynomially many shallow quantum circuits without adaptive measurements. (c) There exists a 2-message proof of quantum depth protocol. Such a protocol allows a classical verifier to efficiently certify that a prover must be performing a computation of some minimum quantum depth. Our proof of quantum depth can be instantiated using the recent proof of quantumness construction by Yamakawa and Zhandry [STOC 22]., Comment: 104 pages (+ 9 page Appendix), 10 figures

We present a classical algorithm that, for any $D$-dimensional geometrically-local, quantum circuit $C$ of polylogarithmic-depth, and any bit string $x \in {0,1}^n$, can compute the quantity $||^2$ to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension $D$. This is an extension of the result [CC21], which originally proved this result for $D = 3$. To see why this is interesting, note that, while the $D = 1$ case of this result follows from standard use of Matrix Product States, known for decades, the $D = 2$ case required novel and interesting techniques introduced in [BGM19]. Extending to the case $D = 3$ was even more laborious and required further new techniques introduced in [CC21]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for $D \leq 3$, we can now handle any fixed dimension $D > 3$. Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate the desired quantity via several instantiations of the same problem type, each involving $D$-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the $D^{th}$ dimension is so small that they can effectively be regarded as $(D-1)$-dimensional problems by absorbing the small width in the $D^{th}$ dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [CC21] still hold in higher dimensions, which requires small modifications to the analysis in some places.

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit $C$ acting on $n$ qubits, and any bit string $x\in\{0,1\}^n$, can compute the quantity $|< x |C|0^{\otimes n}>|^2$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$ additive error [Mov20, KMM21]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for this estimation task restricted to 2D circuits, which makes a novel use of 1D Matrix Product States (MPS) carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted combination of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit ``pieces" produced this way.

A conjecture of Jozsa (arXiv:quant-ph/0508124) states that any polynomial-time quantum computation can be simulated by polylogarithmic-depth quantum computation interleaved with polynomial-depth classical computation. Separately, Aaronson conjectured that there exists an oracle $\mathcal{O}$ such that $\textrm{BQP}^{\mathcal{O}} \neq (\textrm{BPP}^\textrm{BQNC})^{\mathcal{O}}$. These conjectures are intriguing allusions to the unresolved potential of combining classical and low-depth quantum computation. In this work we show that the Welded Tree Problem, which is an oracle problem that can be solved in quantum polynomial time as shown by Childs et al. (arXiv:quant-ph/0209131), cannot be solved in $\textrm{BPP}^{\textrm{BQNC}}$, nor can it be solved in the class that Jozsa describes. This proves Aaronson's oracle separation conjecture and provides a counterpoint to Jozsa's conjecture relative to the Welded Tree oracle problem. More precisely, we define two complexity classes, $\textrm{HQC}$ and $\textrm{JC}$ whose languages are decided by two different families of interleaved quantum-classical circuits. $\textrm{HQC}$ contains $\textrm{BPP}^\textrm{BQNC}$ and is therefore relevant to Aaronson's conjecture, while $\textrm{JC}$ captures the model of computation that Jozsa considers. We show that the Welded Tree Problem gives an oracle separation between either of $\{\textrm{JC}, \textrm{HQC}\}$ and $\textrm{BQP}$. Therefore, even when interleaved with arbitrary polynomial-time classical computation, greater "quantum depth" leads to strictly greater computational ability in this relativized setting., Comment: 39 pages, revised

We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is $\mathrm{NP}$-complete to decide whether the classical value of a non-local game is 1 or $1- \epsilon$. Furthermore, as long as $\epsilon$ is small enough, this result does not depend on the gap $\epsilon$. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap $\epsilon$ decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of $\mathrm{MIP}^{co}(2,1,1,s)$ (proofs with two provers, one round, completeness probability $1$, soundness probability $s$, and commuting-operator strategies) can increase without bound as the gap $1-s$ gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class $\mathrm{PZK}$-$\mathrm{MIP}^{co}_{\delta}(2,1,1,s)$ of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap $1-s$ gets arbitrarily small. While we do not know any computable time upper bound on the class $\mathrm{MIP}^{co}$, a result of the first author and Vidick shows that for $s = 1-1/\text{poly}(f(n))$ and $\delta = 1/\text{poly}(f(n))$, the class $\mathrm{MIP}^{co}_\delta(2,1,1,s)$, with constant communication from the provers, is contained in $\mathrm{TIME}(\exp(\text{poly}(f(n))))$. We give a lower bound of $\mathrm{coNTIME}(f(n))$ (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.

Entanglement assistance is known to reduce the quantum communication complexity of evaluating functions with distributed inputs. But does the type of entanglement matter, or are EPR pairs always sufficient? This is a natural question because in several other settings maximally entangled states are known to be less useful as a resource than some partially entangled state. These include non-local games, tasks with quantum communication between players and referee, and simulating bipartite unitaries or communication channels. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using $Q$ qubits of communication and arbitrary shared entanglement can be $\epsilon$-approximated by a protocol using $O(Q/\epsilon+\log(1/\epsilon)/\epsilon)$ qubits of communication and only EPR pairs as shared entanglement. Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We show that the communication cost of converting between two bipartite quantum states is upper bounded, up to a constant multiplicative factor, by a natural and efficiently computable quantity which we call the $\ell_{\infty}$-Earth Mover's Distance (EMD) between those two states. Furthermore, we prove a complementary lower bound on the cost of state conversion by the $\epsilon$-smoothed $\ell_{\infty}$-EMD, which is a natural smoothing of the $\ell_{\infty}$-EMD that we will define via a connection with optimal transport theory.

The generation of certifiable randomness is the most fundamental information-theoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation or computational assumptions. To demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our proposal does not rest on any complexity-theoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth. Success on our task can be easily verified in classical linear time. Finally, our task is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions., Comment: 36 pages, 2 figures

We show that the $n$-round parallel repetition of the Magic Square game of Mermin and Peres is rigid, in the sense that for any entangled strategy succeeding with probability $1 -\varepsilon$, the players' shared state is $O(\mathrm{poly}(n\varepsilon))$-close to $2n$ EPR pairs under a local isometry. Furthermore, we show that, under local isometry, the players' measurements in said entangled strategy must be $O(\mathrm{poly}(n\varepsilon))$ close to the "ideal" strategy when acting on the shared state., Comment: 29 pages

The class $\MIP^*$ of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Little is known about the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. This hierarchy converges to a value that is only known to coincide with the provers' maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes' embedding conjecture. No bounds on the rate of convergence are known. We introduce a rounding scheme for the hierarchy, establishing that any solution to its $N$-th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by $O(\ell^2/\sqrt{N})$ in operator norm, where $\ell$ is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of $\MIP^*$, called $\MIP_\delta^*$, in which the soundness property is required to hold as long as the commutator of operations performed by distinct provers has norm at most $\delta$. Our rounding scheme implies the upper bound $\MIP_\delta^* \subseteq \DTIME(\exp(\exp(\poly)/\delta^2))$. In terms of lower bounds we establish that $\MIP^*_{2^{-\poly}}$, with completeness $1$ and soundness $1-2^{-\poly}$, contains $\NEXP$. The relationship of $\MIP_\delta^*$ to $\MIPstar$ has connections with the mathematical literature on approximate commutation. Our rounding scheme gives an elementary proof that the Strong Kirchberg Conjecture implies that $\MIPstar$ is computable. We discuss applications to device-independent cryptography.

We present a device-independent randomness expansion protocol, involving only a constant number of non-signaling quantum devices, that achieves \emph{infinite expansion}: starting with $m$ bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is $\exp(-\Omega(m^{1/3}))$-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in $m$). This settles a long-standing open problem in the area of randomness expansion and device-independence. The analysis of our protocols involves overcoming fundamental challenges in the study of \emph{adaptive} device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are \emph{Input Secure}; that is, their output is guaranteed to be secure against a quantum eavesdropper, \emph{even if the input randomness was generated by that same eavesdropper}! The notion of Input Security may be of independent interest to other areas such as device-independent quantum key distribution., Comment: 36 pages; updated references, results unchanged

A recent sequence of works, initially motivated by the study of the nonlocal properties of entanglement, demonstrate that a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short random seed and the ability to ensure that two black-box devices do not communicate (i.e. are non-signaling). We call protocols achieving such certified amplification of a short random seed randomness amplifiers. We introduce a simple framework in which we initiate the systematic study of the possibilities and limitations of randomness amplifiers. Our main results include a new, improved analysis of a robust randomness amplifier with exponential expansion, as well as the first upper bounds on the maximum expansion achievable by a broad class of randomness amplifiers. In particular, we show that non-adaptive randomness amplifiers that are robust to noise cannot achieve more than doubly exponential expansion. Finally, we show that a wide class of protocols based on the use of the CHSH game can only lead to (singly) exponential expansion if adversarial devices are allowed the full power of non-signaling strategies. Our upper bound results apply to all known non-adaptive randomness amplifier constructions to date., Comment: 28 pages. Comments welcome

We generalize the previous results of [1] by proving unfrustration condition and degeneracy of the ground states of qudits (d-dimensional spins) on a k-child tree with generic local interactions. We find that the dimension of the ground space grows doubly exponentially in the region where rk<=(d^2)/4 for k>1. Further, we extend the results in [1] by proving that there are no zero energy ground states when r>(d^2)/4 for k=1 implying that the effective Hamiltonian is invertible., Comment: 13 page, 1 figure