On the efficiency of Hamiltonian-based quantum computation for low-rank matrices

DOI10.1063/1.3690045MaRDI QIDQ2861773zbMATH OpenOpenAlexWikidataFDO

Authors Zhenwei Cao, Alexander Elgart

Publication date 11 November 2013

Published in Journal of Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.4911

zbMATH Keywords

adiabatic quantum computingGrover speedup

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Other types of codes (94B60)

Abstract: We present an extension of Adiabatic Quantum Computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

Recommendations

• Unstructured adiabatic quantum search
• Energy and efficiency of adiabatic quantum search algorithms
• LIMITATIONS OF SOME SIMPLE ADIABATIC QUANTUM ALGORITHMS
• Bounding Run-Times of Local Adiabatic Algorithms
• How fast can quantum annealers count?

Cites work

• scientific article; zbMATH DE number 3732713 (Why is no real title available?)
• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• A STRONG OPERATOR TOPOLOGY ADIABATIC THEOREM
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Adiabatic charge transport and the Kubo formula for Landau-type Hamiltonians
• Adiabatic theorem without a gap condition
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Anderson localization makes adiabatic quantum optimization fail
• Bounds for the adiabatic approximation with applications to quantum computation
• LIMITATIONS OF SOME SIMPLE ADIABATIC QUANTUM ALGORITHMS
• Linear adiabatic theory. Exponential estimates
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Precise exponential estimates in adiabatic theory
• Strengths and Weaknesses of Quantum Computing
• Table of integrals, series, and products. Translated from the Russian. Translation edited and with a preface by Alan Jeffrey and Daniel Zwillinger. With one CD-ROM (Windows, Macintosh and UNIX)

Cited in

(7)

• On the gap of Hamiltonians for the adiabatic simulation of quantum circuits
• Energy and efficiency of adiabatic quantum search algorithms
• A note on the switching adiabatic theorem
• Adapting the traveling salesman problem to an adiabatic quantum computer
• Noise resistance of adiabatic quantum computation using random matrix theory
• Unstructured adiabatic quantum search
• How quantum is the speedup in adiabatic unstructured search?

This page was built for publication: On the efficiency of Hamiltonian-based quantum computation for low-rank matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2861773)