Nonadaptive quantum query complexity

DOI10.1016/J.IPL.2010.09.009MaRDI QIDQ1675876zbMATH OpenOpenAlexWikidataFDO

Authors Ashley Montanaro

Publication date 3 November 2017

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

decision tree complexityquantum computingquantum query complexitytheory of computation

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes some total boolean function depending on n variables must make Omega(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using O(k log m) queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms can achieve at most a very limited speed-up over classical query algorithms.

Recommendations

• Adversary lower bounds for nonadaptive quantum algorithms
• On exact quantum query complexity
• Nondeterministic Quantum Query and Communication Complexities
• Quantum lower bounds by polynomials
• On the power of non-adaptive learning graphs

Cites work

• Adversary Lower Bounds for Nonadaptive Quantum Algorithms
• Complexity measures and decision tree complexity: a survey.
• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• On the Power of Quantum Computation
• Polynomial degree vs. quantum query complexity
• Quantum Complexity Theory
• Quantum lower bounds by polynomials
• Queries and concept learning

Cited in

(11)

• On exact quantum query complexity
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Nondeterministic query algorithms
• On the uselessness of quantum queries
• Quantum query algorithms are completely bounded forms
• Nondeterministic Quantum Query and Communication Complexities
• On the power of non-adaptive learning graphs
• Quantum query algorithms are completely bounded forms
• Mathematical Foundations of Computer Science 2004
• Randomized vs. deterministic separation in time-space tradeoffs of multi-output functions
• Adversary lower bounds for nonadaptive quantum algorithms

This page was built for publication: Nonadaptive quantum query complexity

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