Quantum search on bounded-error inputs

DOI10.1007/3-540-45061-0_25MaRDI QIDQ4449183zbMATH OpenFDO

Authors Peter Høyer, Michele Mosca, Ronald de Wolf

Publication date 8 February 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2719/27190291.htm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 2103524
• Unconventional Computation
• Quantum lower bounds by polynomials
• A panoply of quantum algorithms

Cited in

(32)

• Claw finding algorithms using quantum walk
• Sharp error bounds on quantum Boolean summation in various settings
• Quantum search with variable times
• Quantum algorithms for string processing
• Quantum algorithm for Dyck language with multiple types of brackets
• Extended learning graphs for triangle finding
• Polynomial degree vs. quantum query complexity
• Quantum walks can find a marked element on any graph
• Exact quantum query algorithm for error detection code verification
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Hardness amplification and the approximate degree of constant-depth circuits
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• Quantum Walk Based Search Algorithms
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Quantum pattern matching fast on average
• On the robustness of bucket brigade quantum RAM
• On the robustness of bucket brigade quantum RAM
• Unconventional Computation
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Unbounded-error quantum computation with small space bounds
• Quantum bounds for 2D-grid and Dyck language
• Quantum algorithm for lexicographically minimal string rotation
• Near-optimal quantum algorithms for string problems
• Provable dual attacks on learning with errors
• A note on quantum divide and conquer for minimal string rotation
• Quantum algorithms for Hopcroft's problem
• Quantum approximate k-minimum finding
• On the quantum time complexity of divide and conquer
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Improved algorithms for quantum identification of Boolean oracles

This page was built for publication: Quantum search on bounded-error inputs

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