DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2015.163

A Universal Adiabatic Quantum Query Algorithm

Authors: Mathieu Brandeho and Jérémie Roland

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract

Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete-time model of quantum computation, it also holds for continuous-time (or Hamiltonian-based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern technique of theoretical computer science, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest's theorem, while the upper bound relies on the adiabatic theorem, as it goes by constructing a universal adiabatic quantum query algorithm. Another originality is that we use for the first time in the context of quantum computation a version of the adiabatic theorem that does not require a spectral gap.

Cite as

Mathieu Brandeho and Jérémie Roland. A Universal Adiabatic Quantum Query Algorithm. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 163-179, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brandeho_et_al:LIPIcs.TQC.2015.163,
  author =	{Brandeho, Mathieu and Roland, J\'{e}r\'{e}mie},
  title =	{{A Universal Adiabatic Quantum Query Algorithm}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{163--179},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.163},
  URN =		{urn:nbn:de:0030-drops-55556},
  doi =		{10.4230/LIPIcs.TQC.2015.163},
  annote =	{Keywords: Quantum Algorithms, Query Complexity, Adiabatic Quantum Computation, Adversary Method}
}

Search Results

Documents authored by Brandeho, Mathieu

A Universal Adiabatic Quantum Query Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message