@article {3356, title = {Hamiltonians whose low-energy states require $\Omega(n)$ T gates}, year = {2023}, month = {10/2/2023}, abstract = {

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 ω(logn) 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 Ω(n) T gates. Following a previous work [CCNN23], 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 Ω(logn)-depth and Ω(n) T gates to prepare. Our results utilize a connection between T-count and stabilizer groups, which was recently applied in the context of learning low T-count states [GIKL23a, GIKL23b, GIKL23c].

}, url = {https://arxiv.org/abs/2310.01347}, author = {Nolan J. Coble and Matthew Coudron and Jon Nelson and Seyed Sajjad Nezhadi} } @article {3252, title = {Local Hamiltonians with no low-energy stabilizer states}, year = {2023}, month = {2/28/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2302.14755}, author = {Nolan J. Coble and Matthew Coudron and Jon Nelson and Seyed Sajjad Nezhadi} } @article {3001, title = {Approximating Output Probabilities of Shallow Quantum Circuits which are Geometrically-local in any Fixed Dimension}, journal = {Leibniz International Proceedings in Informatics (LIPIcs)}, volume = {232}, year = {2022}, month = {4/7/2022}, pages = {9:1--9:17}, type = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, abstract = {

We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x\∈0,1n, can compute the quantity |\<x|C|0\⊗n\>|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\≤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 Dth dimension is so small that they can effectively be regarded as (D\−1)-dimensional problems by absorbing the small width in the Dth 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.

}, keywords = {Computational Complexity (cs.CC), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)}, isbn = {978-3-95977-237-2}, issn = {1868-8969}, doi = {10.48550/ARXIV.2202.08349}, url = {https://arxiv.org/abs/2202.08349}, author = {Dontha, Suchetan and Tan, Shi Jie Samuel and Smith, Stephen and Choi, Sangheon and Matthew Coudron} } @article {2775, title = {Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits}, journal = {Communications in Mathematical Physics}, volume = {382}, year = {2021}, month = {2/9/2021}, pages = {49 - 86}, abstract = {

The generation of certifiable randomness is the most fundamental informationtheoretic 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 and more recent proposals for randomness certification based on computational\ assumptions. Furthermore, 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 362(6412):308\–311,\ 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 results lead to a new proposal for a demonstrated quantum advantage\ that has some advantages compared to existing proposals. First, 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. Second, 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.

}, issn = {0010-3616}, doi = {10.1007/s00220-021-03963-w}, url = {https://link.springer.com/content/pdf/10.1007/s00220-021-03963-w.pdf}, author = {Matthew Coudron and Stark, Jalex and Vidick, Thomas} } @article {2573, title = {Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)}, journal = {Accepted to the Symposium on the Theory of Computing (STOC) 2020 conference}, year = {2020}, month = {4/23/2020}, abstract = {

A conjecture of Jozsa [Jozsa06] states that any polynomial-time quantum computation can be simulated by polylogarithmic-depth quantum computation interleaved with polynomial-depth classical computation. Separately, Aaronson [Aaronson05, Aaronson11, Aaronson14] conjectured that there exists an oracle O such that BQPO\≠(BPPBQNC)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. [ChildsCDFGS03], cannot be solved in BPPBQNC, nor can it be solved in the class that Jozsa describes. This proves Aaronson\&$\#$39;s oracle separation conjecture and provides a counterpoint to Jozsa\&$\#$39;s conjecture relative to the Welded Tree oracle problem. More precisely, we define two complexity classes, HQC and JC whose languages are decided by two different families of interleaved quantum-classical circuits. HQC contains BPPBQNC and is therefore relevant to Aaronson\&$\#$39;s conjecture, while JC captures the model of computation that Jozsa considers. We show that the Welded Tree Problem gives an oracle separation between either of {JC,HQC} and BQP. Therefore, even when interleaved with arbitrary polynomial-time classical computation, greater \"quantum depth\" leads to strictly greater computational ability in this relativized setting.

}, doi = {https://doi.org/10.1145/3357713.3384269}, url = {https://arxiv.org/abs/1909.10503}, author = {Matthew Coudron and Sanketh Menda} } @article {2716, title = {Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits}, journal = {Accepted to QIP 2021}, year = {2020}, month = {12/10/2020}, abstract = {

We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit C, and any bit string x\∈{0,1}n, can compute the quantity |\<x|C|0\⊗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\−n2 additive error [Mov20]. The previous best known algorithm for this problem used O(2n1/3poly(1/ε)) time to compute probabilities to within additive error ε [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States 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, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit \"pieces\" produced this way.

}, url = {https://arxiv.org/abs/2012.05460}, author = {Nolan J. Coble and Matthew Coudron} } @article {2820, title = {Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits}, year = {2020}, month = {12/10/2020}, abstract = {

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\∈{0,1}n, can compute the quantity |\<x|C|0\⊗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\−n2 additive error [Mov20, KMM21]. The previous best known algorithm for this problem used O(2n1/3poly(1/ϵ)) time to compute probabilities to within additive error ϵ [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 {\textquoteleft}{\textquoteleft}pieces\" produced this way.

}, url = {https://arxiv.org/abs/2012.05460}, author = {Nolan J. Coble and Matthew Coudron} }