Adiabatic quantum counting by geometric phase estimation

DOI10.1007/S11128-009-0132-YMaRDI QIDQ989904zbMATHOpenAlexFDO

Authors Chi Zhang, A. Papageorgiou, Zhaohui Wei

Publication date 23 August 2010

Published in Quantum Information Processing (Search for Journal in Brave)

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

zbMATH Keywords

counting problemBerry phasephase estimationadiabatic quantum algorithm

Mathematics Subject Classification ID

Quantum computation (81P68) Classical and relativistic thermodynamics (80A10) Differential geometric methods, including holonomy, Berry and Hannay phases, Aharonov-Bohm effect, etc. in quantum theory (81Q70)

Abstract: We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $alpha$, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2pialpha$. By estimating the Berry phase, we can approximate $alpha$, and solve the problem. For an error bound $epsilon$, the algorithm can solve the problem with cost of order $(frac1epsilon{)}^{3/2}$, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.

Recommendations

• How fast can quantum annealers count?
• Quantum counting: algorithm and error distribution
• Counting by quantum eigenvalue estimation
• Generalized quantum counting algorithm for non-uniform amplitude distribution
• Unstructured adiabatic quantum search

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3116475 (Why is no real title available?)
• scientific article; zbMATH DE number 5320186 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 1790425 (Why is no real title available?)
• Classical and quantum complexity of the Sturm-Liouville eigenvalue problem
• Colloquium: Quantum annealing and analog quantum computation
• Noise resistance of adiabatic quantum computation using random matrix theory
• Quantal phase factors accompanying adiabatic changes
• Quantum summation with an application to integration.
• The quantum query complexity of approximating the median and related statistics

Cited in

(1)

• Hamiltonian dynamics and adiabatic invariants for time-dependent superconducting qubit-oscillators and resonators in quantum computing systems

This page was built for publication: Adiabatic quantum counting by geometric phase estimation

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