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

quantum computingtheory of computationquantum query complexitydecision tree complexity

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

• scientific article; zbMATH DE number 5605071 (Why is no real title available?)
• Adversary Lower Bounds for Nonadaptive Quantum Algorithms
• Complexity measures and decision tree complexity: a survey.
• 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

(10)

• On the uselessness of quantum queries
• Quantum query algorithms are completely bounded forms
• Nondeterministic query algorithms
• Quantum query algorithms are completely bounded forms
• Nondeterministic Quantum Query and Communication Complexities
• Adversary lower bounds for nonadaptive quantum algorithms
• On exact quantum query complexity
• On the power of non-adaptive learning graphs
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Mathematical Foundations of Computer Science 2004

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)