Nonadaptive quantum query complexity

DOI10.1016/J.IPL.2010.09.009zbMATH Open1379.68135arXiv1001.0018OpenAlexW2133905777WikidataQ58478286 ScholiaQ58478286MaRDI QIDQ1675876FDOQ1675876

Authors: Ashley Montanaro 

Publication date: 3 November 2017

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

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.

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

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

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)

Cites Work

• Queries and concept learning
• On the Power of Quantum Computation
• Quantum Complexity Theory
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds by polynomials
• Polynomial degree vs. quantum query complexity
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2004
• Adversary Lower Bounds for Nonadaptive Quantum Algorithms

Cited In (10)

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

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)