Forrelation: a problem that optimally separates quantum from classical computing
From MaRDI portal
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
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(26)- Quantum query as a state decomposition
- Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
- Optimal separation in exact query complexities for Simon's problem
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
- Quantum versus randomized communication complexity, with efficient players
- A relational time-symmetric framework for analyzing the quantum computational speedup
- Time evolution of complexity: a critique of three methods
- Parity decision tree in classical-quantum separations for certain classes of Boolean functions
- Forrelation: a problem that optimally separates quantum from classical computing
- Quantum query algorithms are completely bounded forms
- Quantum query algorithms are completely bounded forms
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- scientific article; zbMATH DE number 7561499 (Why is no real title available?)
- Oracle separation of BQP and PH
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- Following forrelation -- quantum algorithms in exploring Boolean functions' spectra
- Introducing nega-forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra
- Lifting query complexity to time-space complexity for two-way finite automata
- Quantum depth in the random oracle model
- Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms
- Quantum advantage from one-way functions
- Symmetries, graph properties, and quantum speedups
- A review on quantum Fourier transform
- Learning low-degree quantum objects
- A cb-Bohnenblust-Hille inequality with constant one and its applications in learning theory
- Quantum versus randomized communication complexity, with efficient players
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 Q2941519)
