On exact quantum query complexity
From MaRDI portal
Publication:2350895
Abstract: We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits. We also characterise the model of nonadaptive exact quantum query complexity in terms of coding theory and completely characterise the query complexity of symmetric boolean functions in this context. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes. We include numerical results giving the optimal success probabilities achievable by quantum algorithms computing all boolean functions on up to 4 bits, and all symmetric boolean functions on up to 6 bits.
Recommendations
Cites work
- Automata, Languages and Programming
- Complexity measures and decision tree complexity: a survey.
- Covering radius---Survey and recent results
- Exact quantum query algorithm for error detection code verification
- Exact quantum query complexity of EXACT and THRESHOLD
- scientific article; zbMATH DE number 5605071 (Why is no real title available?)
- scientific article; zbMATH DE number 5485488 (Why is no real title available?)
- scientific article; zbMATH DE number 5485521 (Why is no real title available?)
- Matrix Analysis
- Nonadaptive quantum query complexity
- On exact quantum query complexity
- On the degree of Boolean functions as real polynomials
- On the Power of Quantum Computation
- Quantum algorithms revisited
- Quantum Complexity Theory
- Quantum lower bound for recursive Fourier sampling
- Quantum lower bounds by polynomials
- Rapid solution of problems by quantum computation
- Reflections for quantum query algorithms
- Superlinear advantage for exact quantum algorithms
- The quantum black-box complexity of majority
Cited in
(44)- Quantum query as a state decomposition
- Optimal separation in exact query complexities for Simon's problem
- Nonadaptive quantum query complexity
- Sharp quantum versus classical query complexity separations
- The power of various real-valued quantum queries
- Evaluation of exact quantum query complexities by semidefinite programming
- An exact quantum algorithm for a restricted subtraction game
- Revisiting Deutsch-Jozsa algorithm
- On exact quantum query complexity
- Polynomial degree vs. quantum query complexity
- From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
- On a poset of quantum exact promise problems
- Parity decision tree in classical-quantum separations for certain classes of Boolean functions
- Superlinear advantage for exact quantum algorithms
- The quantum query complexity of approximating the median and related statistics
- Exact quantum query algorithm for error detection code verification
- From quantum query complexity to state complexity
- Exact quantum query complexity of EXACT and THRESHOLD
- Exact quantum query complexity of \(\mathrm{EXACT}_{k,l}^n\)
- Generalizations of the distributed Deutsch-Jozsa promise problem
- Computational Complexity of Quantum Satisfiability
- scientific article; zbMATH DE number 6667586 (Why is no real title available?)
- Query complexity in expectation
- A strong direct product theorem for quantum query complexity
- scientific article; zbMATH DE number 1756014 (Why is no real title available?)
- A note on the quantum query complexity of permutation symmetric functions
- Understanding quantum algorithms via query complexity
- Algorithms and Computation
- Superlinear advantage for exact quantum algorithms
- Recent developments in quantum algorithms and complexity
- Quantum and classical query complexities of local search are polynomially related
- SOFSEM 2004: Theory and Practice of Computer Science
- Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability
- Lifting query complexity to time-space complexity for two-way finite automata
- scientific article; zbMATH DE number 7716601 (Why is no real title available?)
- Unbounded-error quantum query complexity
- Characterization of exact two-query quantum algorithms
- On the fine-grained query complexity of symmetric functions
- Distributed generalized Deutsch-Jozsa algorithm
- Sensitivity of symmetric Boolean functions
- On the fine-grained query complexity of symmetric functions
- On the quantum query complexity of local search in two and three dimensions
- The quantum setting with randomized queries for continuous problems
- The quantum query complexity of elliptic PDE
This page was built for publication: On exact quantum query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350895)
