Exact quantum lower bound for Grover's problem

MaRDI QIDQ3633954zbMATH OpenFDO

Authors

Publication date 23 June 2009

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

zbMATH Keywords

decision treesGrover's algorithmlower boundquantum computing

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum computation (81P68) Markov and semi-Markov decision processes (90C40)

Recommendations

• An upper bound on the rate of information transfer by Grover's oracle
• An Upper Bound on the Rate of Information Transfer by Grover’s Oracle
• Quantum lower bounds by quantum arguments
• Quantum lower bounds by quantum arguments
• Exact quantum search by parallel unitary discrimination schemes

Cited in

(15)

• A lower bound for quantum search of an ordered list
• Solving binary \(\mathcal {MQ}\) with Grover's algorithm
• Lower bound for quantum phase estimation
• An upper bound on the rate of information transfer by Grover's oracle
• Lower bounds of a quantum search for an extreme point
• Exact quantum search by parallel unitary discrimination schemes
• The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
• Strategies for quantum races
• An Upper Bound on the Rate of Information Transfer by Grover’s Oracle
• Deriving Grover's lower bound from simple physical principles
• Quantum lower bounds by quantum arguments
• Phase shift and multi-controlled \(Z\)-type gates
• A non-heuristic approach to time-space tradeoffs and optimizations for BKW
• Quantum one-wayness of the single-round sponge with invertible permutations
• Generalized hybrid search with applications to blockchains and hash function security

This page was built for publication: Exact quantum lower bound for Grover's problem

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