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

DOI10.1063/1.3690045zbMATH Open1274.81056arXiv1004.4911OpenAlexW3102711566WikidataQ58004536 ScholiaQ58004536MaRDI QIDQ2861773FDOQ2861773

Authors: Zhenwei Cao, Alexander Elgart 

Publication date: 11 November 2013

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

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.

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

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?

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)

Cites Work

• Title not available (Why is that?)
• 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)
• An elementary proof of a theorem of Johnson and Lindenstrauss
• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Adiabatic theorem without a gap condition
• Bounds for the adiabatic approximation with applications to quantum computation
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Title not available (Why is that?)
• Strengths and Weaknesses of Quantum Computing
• Linear adiabatic theory. Exponential estimates
• Anderson localization makes adiabatic quantum optimization fail
• Precise exponential estimates in adiabatic theory
• LIMITATIONS OF SOME SIMPLE ADIABATIC QUANTUM ALGORITHMS
• Adiabatic charge transport and the Kubo formula for Landau-type Hamiltonians
• A STRONG OPERATOR TOPOLOGY ADIABATIC THEOREM

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)