LIMITATIONS OF SOME SIMPLE ADIABATIC QUANTUM ALGORITHMS

DOI10.1142/S0219749908003724MaRDI QIDQ3534100zbMATH OpenOpenAlexFDO

Authors Lawrence M. Ioannou, Michele Mosca

Publication date 3 November 2008

Published in International Journal of Quantum Information (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0702241

zbMATH Keywords

adiabaticboundsquantum

Mathematics Subject Classification ID

Adiabatic invariants for problems in Hamiltonian and Lagrangian mechanics (70H11) Quantum computation (81P68)

Abstract: Let $H(t)=(1-t/T)H_0+(t/T)H_1$, $tin[0,T]$, be the Hamiltonian governing an adiabatic quantum algorithm, where $H_0$ is diagonal in the Hadamard basis and $H_1$ is diagonal in the computational basis. We prove that $H_0$ and $H_1$ must each have at least two large mutually-orthogonal eigenspaces if the algorithm's running time is to be subexponential in the number of qubits. We also reproduce the optimality proof of Farhi and Gutmann's search algorithm in the context of this adiabatic scheme; because we only consider initial Hamiltonians that are diagonal in the Hadamard basis, our result is slightly stronger than the original.

Recommendations

• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
• Bounding Run-Times of Local Adiabatic Algorithms
• scientific article; zbMATH DE number 1984609
• Energy and efficiency of adiabatic quantum search algorithms
• The quantum adiabatic optimization algorithm and local minima

Cites work

• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)

Cited in

(9)

• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Efficient diabatic quantum algorithm in number factorization
• Entanglement sudden death and birth effects in two qubits maximally entangled mixed states under quantum channels
• On the optimal schedule of adiabatic quantum computing
• On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
• The quantum adiabatic optimization algorithm and local minima
• Bounding Run-Times of Local Adiabatic Algorithms
• Synthesis of quantum circuits for linear nearest neighbor architectures

This page was built for publication: LIMITATIONS OF SOME SIMPLE ADIABATIC QUANTUM ALGORITHMS

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