Forrelation is extremally hard
From MaRDI portal
Cites work
- A Pseudorandom Generator from any One-way Function
- An Optimal Separation of Randomized and Quantum Query Complexity
- Bounds for small-error and zero-error quantum algorithms
- BQP and the polynomial hierarchy
- Complexity-theoretic foundations of quantum supremacy experiments
- EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
- Exponential algorithmic speedup by a quantum walk
- Following forrelation -- quantum algorithms in exploring Boolean functions' spectra
- Forrelation: a problem that optimally separates quantum from classical computing
- Four decades of research on bent functions
- scientific article; zbMATH DE number 6679846 (Why is no real title available?)
- scientific article; zbMATH DE number 6297720 (Why is no real title available?)
- scientific article; zbMATH DE number 7768397 (Why is no real title available?)
- k-forrelation optimally separates Quantum and classical query complexity
- On the Power of Quantum Computation
- Oracle Separation of BQP and PH
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Property testing bounds for linear and quadratic functions via parity decision trees
- Quantum Complexity Theory
- Quantum cryptography in Algorithmica
- Quantum versus randomized communication complexity, with efficient players
- Rapid solution of problems by quantum computation
- Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem
- Separations in query complexity based on pointer functions
- Superlinear advantage for exact quantum algorithms
- The acrobatics of BQP
- The query complexity of order-finding
- Tight lower bounds for testing linear isomorphism
- Towards optimal separations between quantum and randomized query complexities
- Trade-offs between entanglement and communication
This page was built for publication: Forrelation is extremally hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445598)