3 Search Results for "Cade, Chris"


Document
Track A: Algorithms, Complexity and Games
Improved Hardness Results for the Guided Local Hamiltonian Problem

Authors: Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

Cite as

Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. Improved Hardness Results for the Guided Local Hamiltonian Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{cade_et_al:LIPIcs.ICALP.2023.32,
  author =	{Cade, Chris and Folkertsma, Marten and Gharibian, Sevag and Hayakawa, Ryu and Le Gall, Fran\c{c}ois and Morimae, Tomoyuki and Weggemans, Jordi},
  title =	{{Improved Hardness Results for the Guided Local Hamiltonian Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.32},
  URN =		{urn:nbn:de:0030-drops-180840},
  doi =		{10.4230/LIPIcs.ICALP.2023.32},
  annote =	{Keywords: Quantum computing, Quantum advantage, Quantum Chemistry, Guided Local Hamiltonian Problem}
}
Document
Applications of the Quantum Algorithm for st-Connectivity

Authors: Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)


Abstract
We present quantum algorithms for various problems related to graph connectivity. We give simple and query-optimal algorithms for cycle detection and odd-length cycle detection (bipartiteness) using a reduction to st-connectivity. Furthermore, we show that our algorithm for cycle detection has improved performance under the promise of large circuit rank or a small number of edges. We also provide algorithms for detecting even-length cycles and for estimating the circuit rank of a graph. All of our algorithms have logarithmic space complexity.

Cite as

Kai DeLorenzo, Shelby Kimmel, and R. Teal Witter. Applications of the Quantum Algorithm for st-Connectivity. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{delorenzo_et_al:LIPIcs.TQC.2019.6,
  author =	{DeLorenzo, Kai and Kimmel, Shelby and Witter, R. Teal},
  title =	{{Applications of the Quantum Algorithm for st-Connectivity}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.6},
  URN =		{urn:nbn:de:0030-drops-103984},
  doi =		{10.4230/LIPIcs.TQC.2019.6},
  annote =	{Keywords: graphs, algorithms, query complexity, quantum algorithms, span programs}
}
Document
The Quantum Complexity of Computing Schatten p-norms

Authors: Chris Cade and Ashley Montanaro

Published in: LIPIcs, Volume 111, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)


Abstract
We consider the quantum complexity of computing Schatten p-norms and related quantities, and find that the problem of estimating these quantities is closely related to the one clean qubit model of computation. We show that the problem of approximating Tr(|A|^p) for a log-local n-qubit Hamiltonian A and p=poly(n), up to a suitable level of accuracy, is contained in DQC1; and that approximating this quantity up to a somewhat higher level of accuracy is DQC1-hard. In some cases the level of accuracy achieved by the quantum algorithm is substantially better than a natural classical algorithm for the problem. The same problem can be solved for arbitrary sparse matrices in BQP. One application of the algorithm is the approximate computation of the energy of a graph.

Cite as

Chris Cade and Ashley Montanaro. The Quantum Complexity of Computing Schatten p-norms. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{cade_et_al:LIPIcs.TQC.2018.4,
  author =	{Cade, Chris and Montanaro, Ashley},
  title =	{{The Quantum Complexity of Computing Schatten p-norms}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-080-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{111},
  editor =	{Jeffery, Stacey},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.4},
  URN =		{urn:nbn:de:0030-drops-92513},
  doi =		{10.4230/LIPIcs.TQC.2018.4},
  annote =	{Keywords: Schatten p-norm, quantum complexity theory, complexity theory, one clean qubit model}
}
  • Refine by Author
  • 2 Cade, Chris
  • 1 DeLorenzo, Kai
  • 1 Folkertsma, Marten
  • 1 Gharibian, Sevag
  • 1 Hayakawa, Ryu
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Quantum query complexity

  • Refine by Keyword
  • 1 Guided Local Hamiltonian Problem
  • 1 Quantum Chemistry
  • 1 Quantum advantage
  • 1 Quantum computing
  • 1 Schatten p-norm
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail