Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
From MaRDI portal
Publication:4571925
DOI10.1137/15M1050902zbMATH Open1396.68047arXiv1411.5729OpenAlexW2811282363WikidataQ129620874 ScholiaQ129620874MaRDI QIDQ4571925FDOQ4571925
Scott Aaronson, Andris Ambainis
Publication date: 4 July 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Abstract: We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs ~sqrt(N)/log(N) queries (improving an ~N^{1/4} lower bound of Aaronson). Conversely, we show that this 1 versus ~sqrt(N) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N^{1-1/2t})-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus ~N^{1-1/2t} separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."
Full work available at URL: https://arxiv.org/abs/1411.5729
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exponential algorithmic speedup by a quantum walk
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- Exponential separation of quantum and classical communication complexity
- Quantum Property Testing
- The query complexity of order-finding
- Complexity measures and decision tree complexity: a survey.
- Quantum lower bounds by polynomials
- Improved direct product theorems for randomized query complexity
- Polynomial degree vs. quantum query complexity
- BQP and the polynomial hierarchy
- Sharp quantum versus classical query complexity separations
- Polynomials, quantum query complexity, and Grothendieck's inequality
- On the role of Hadamard gates in quantum circuits
- Forrelation
- On the fourier tails of bounded functions over the discrete cube
- New results on quantum property testing
- Polynomial bounds for decoupling, with applications
Cited In (8)
- Query-to-Communication Lifting for BPP
- Verifying quantum computations at scale: A cryptographic leash on quantum devices
- An Optimal Separation of Randomized and Quantum Query Complexity
- Strong dispersion property for the quantum walk on the hypercube
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Query complexity of generalized Simon's problem
- Towards quantum computing based community detection
- Quantum cryptography in Algorithmica
This page was built for publication: Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4571925)
