Document

**Published in:** LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [Sevag Gharibian and François {Le Gall}, 2022] 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 [Anshu et al., 2022], 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.

Nolan J. Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi. Local Hamiltonians with No Low-Energy Stabilizer States. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{coble_et_al:LIPIcs.TQC.2023.14, author = {Coble, Nolan J. and Coudron, Matthew and Nelson, Jon and Nezhadi, Seyed Sajjad}, title = {{Local Hamiltonians with No Low-Energy Stabilizer States}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {14:1--14:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-283-9}, ISSN = {1868-8969}, year = {2023}, volume = {266}, editor = {Fawzi, Omar and Walter, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.14}, URN = {urn:nbn:de:0030-drops-183243}, doi = {10.4230/LIPIcs.TQC.2023.14}, annote = {Keywords: Hamiltonian complexity, Stabilizer codes, Low-energy states} }

Document

**Published in:** LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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 [Andrew M. Childs et al., 2003]. 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.

Andrew M. Childs, Matthew Coudron, and Amin Shiraz Gilani. Quantum Algorithms and the Power of Forgetting. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{childs_et_al:LIPIcs.ITCS.2023.37, author = {Childs, Andrew M. and Coudron, Matthew and Gilani, Amin Shiraz}, title = {{Quantum Algorithms and the Power of Forgetting}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {37:1--37:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.37}, URN = {urn:nbn:de:0030-drops-175408}, doi = {10.4230/LIPIcs.ITCS.2023.37}, annote = {Keywords: Quantum algorithms, quantum query complexity} }

Document

**Published in:** LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity |<x|C|0^{⊗ n}>|² to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [Nolan J. Coble and Matthew Coudron, 2021], 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 a standard use of Matrix Product States, known for decades, the D = 2 case required novel and interesting techniques introduced in [Sergy Bravyi et al., 2020]. Extending to the case D = 3 was even more laborious, and required further new techniques introduced in [Nolan J. Coble and Matthew Coudron, 2021]. 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 [Nolan J. Coble and Matthew Coudron, 2021] 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 [Nolan J. Coble and Matthew Coudron, 2021] still hold in higher dimensions, which requires small modifications to the analysis in some places. Our work also includes some simplifications, corrections and clarifications of the use of block-encodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021].

Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi, and Matthew Coudron. Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dontha_et_al:LIPIcs.TQC.2022.9, author = {Dontha, Suchetan and Tan, Shi Jie Samuel and Smith, Stephen and Choi, Sangheon and Coudron, Matthew}, title = {{Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension}}, booktitle = {17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-237-2}, ISSN = {1868-8969}, year = {2022}, volume = {232}, editor = {Le Gall, Fran\c{c}ois and Morimae, Tomoyuki}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.9}, URN = {urn:nbn:de:0030-drops-165163}, doi = {10.4230/LIPIcs.TQC.2022.9}, annote = {Keywords: Low-Depth Quantum Circuits, Matrix Product States, Block-Encoding} }

Document

**Published in:** LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

In this work we consider the role of entanglement assistance in quantum communication protocols, focusing, in particular, on whether the type of shared entangled state can affect the quantum communication complexity of a function. This question is interesting because in some other settings in quantum information, such as non-local games, or tasks that involve quantum communication between players and referee, or simulating bipartite unitaries or communication channels, maximally entangled states are known to be less useful as a resource than some partially entangled states. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a partial or total 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. This conclusion is opposite of the common wisdom in the study of non-local games, where it has been shown, for example, that the I3322 inequality has a non-local strategy using a non-maximally entangled state, which surpasses the winning probability achievable by any strategy using a maximally entangled state of any dimension [Vidick and Wehner, 2011]. We leave open the question of how much the use of a shared maximally entangled state can reduce the quantum communication complexity of a function.
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 give simple and efficiently computable upper and lower bounds. Given two bipartite states |chi> and |upsilon>, we define a natural quantity, d_{infty}(|chi>, |upsilon>), which we call the l_{infty} Earth Mover’s distance, and we show that the communication cost of converting between |chi> and |upsilon> is upper bounded by a constant multiple of d_{infty}(|chi>, |upsilon>). Here d_{infty}(|chi>, |upsilon>) may be informally described as the minimum over all transports between the log of the Schmidt coefficients of |chi> and those of |upsilon>, of the maximum distance that any amount of mass must be moved in that transport. A precise definition is given in the introduction. Furthermore, we prove a complementary lower bound on the cost of state conversion by the epsilon-Smoothed l_{infty}-Earth Mover’s Distance, which is a natural smoothing of the l_{infty}-Earth Mover’s Distance that we will define via a connection with optimal transport theory.

Matthew Coudron and Aram W. Harrow. Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{coudron_et_al:LIPIcs.CCC.2019.20, author = {Coudron, Matthew and Harrow, Aram W.}, title = {{Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {20:1--20:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.20}, URN = {urn:nbn:de:0030-drops-108421}, doi = {10.4230/LIPIcs.CCC.2019.20}, annote = {Keywords: Entanglement, quantum communication complexity} }

Document

**Published in:** LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local game is 1 or 1- epsilon, promised that one of the two is the case. 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 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 PZK-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 MIP^{co}, a result of the first author and Vidick shows that for s = 1-1/poly(f(n)) and delta = 1/poly(f(n)), the class MIP^{co}_delta(2,1,1,s), with constant communication from the provers, is contained in TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.

Matthew Coudron and William Slofstra. Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{coudron_et_al:LIPIcs.CCC.2019.25, author = {Coudron, Matthew and Slofstra, William}, title = {{Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {25:1--25:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.25}, URN = {urn:nbn:de:0030-drops-108478}, doi = {10.4230/LIPIcs.CCC.2019.25}, annote = {Keywords: Quantum complexity theory, Non-local game, Multi-prover interactive proof, Entanglement} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail