Forrelation: a problem that optimally separates quantum from classical computing
From MaRDI portal
Publication:4571925
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."
Recommendations
- Forrelation: a problem that optimally separates quantum from classical computing
- Sharp quantum versus classical query complexity separations
- Separations in query complexity using cheat sheets
- Oracle separation of BQP and PH
- Quantum and classical query complexities for generalized Deutsch-Jozsa problems
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- BQP and the polynomial hierarchy
- Both Toffoli and Controlled-NOT need little help to universal quantum computing
- Complexity measures and decision tree complexity: a survey.
- Complexity-theoretic foundations of quantum supremacy experiments
- Exponential algorithmic speedup by a quantum walk
- Exponential separation of quantum and classical communication complexity
- Forrelation: a problem that optimally separates quantum from classical computing
- Improved direct product theorems for randomized query complexity
- New results on quantum property testing
- On the Fourier tails of bounded functions over the discrete cube
- On the role of Hadamard gates in quantum circuits
- Polynomial bounds for decoupling, with applications
- Polynomial degree vs. quantum query complexity
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Polynomials, quantum query complexity, and Grothendieck's inequality
- Quantum Property Testing
- Quantum lower bounds by polynomials
- Reflections for quantum query algorithms
- Sharp quantum versus classical query complexity separations
- Strengths and Weaknesses of Quantum Computing
- The query complexity of order-finding
Cited in
(10)- Strong dispersion property for the quantum walk on the hypercube
- Query-to-communication lifting for BPP
- Quantum cryptography in Algorithmica
- Forrelation: a problem that optimally separates quantum from classical computing
- An Optimal Separation of Randomized and Quantum Query Complexity
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Query complexity of generalized Simon's problem
- Verifying quantum computations at scale: a cryptographic leash on quantum devices
- Towards quantum computing based community detection
- Introducing nega-forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra
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)
