Lower bound for quantum phase estimation

DOI10.1103/PHYSREVA.71.042313MaRDI QIDQ3102418zbMATH OpenOpenAlexWikidataFDO

Authors Arvid J. Bessen

Publication date 4 December 2011

Published in Physical Review A (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Quantum measurement theory, state operations, state preparations (81P15) Quantum computation (81P68) Quantum stochastic calculus (81S25)

Abstract: We obtain a query lower bound for quantum algorithms solving the phase estimation problem. Our analysis generalizes existing lower bound approaches to the case where the oracle Q is given by controlled powers Q^p of Q, as it is for example in Shor's order finding algorithm. In this setting we will prove a log (1/epsilon) lower bound for the number of applications of Q^p1, Q^p2, ... This bound is tight due to a matching upper bound. We obtain the lower bound using a new technique based on frequency analysis.

Recommendations

• Quantum lower bounds by quantum arguments
• Quantum lower bounds by quantum arguments
• Exact quantum lower bound for Grover's problem
• Quantum lower bounds by polynomials
• QUANTUM PHASE ESTIMATION WITH AN ARBITRARY NUMBER OF QUBITS

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• Quantum approximation. I: Embeddings of finite-dimensional \(L_{p}\) spaces
• Quantum approximation. II: Sobolev embeddings
• Quantum complexity of integration
• Quantum integration in Sobolev classes
• Quantum summation with an application to integration.
• Strengths and Weaknesses of Quantum Computing
• The power of various real-valued quantum queries
• Tractability of approximation for weighted Korobov spaces on classical and quantum computers

Cited in

(13)

• Selecting efficient phase estimation with constant-precision phase shift operators
• Quantum lower bounds by entropy numbers
• On the complexity of the multivariate Sturm-Liouville eigenvalue problem
• Lower bound of quantum uncertainty from extractable classical information
• Some error analysis for the quantum phase estimation algorithms
• Application of distributed semi-quantum computing model in phase estimation
• Improvements in quantum SDP-solving with applications
• Deriving Grover's lower bound from simple physical principles
• Quantum lower bounds by quantum arguments
• Quantum lattice enumeration in limited depth
• Quantum lower bounds by sample-to-query lifting
• The quantum setting with randomized queries for continuous problems
• A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer

This page was built for publication: Lower bound for quantum phase estimation

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