Quantum lower bound for recursive Fourier sampling

MaRDI QIDQ3522430zbMATH OpenFDO

Authors Scott Aaronson

Publication date 3 September 2008

Mathematics Subject Classification ID

Quantum computation (81P68) Search theory (90B40)

Recommendations

• The polynomial degree of recursive Fourier sampling
• Oracle separation of BQP and PH
• Quantum lower bounds by polynomials
• BQP and the polynomial hierarchy
• Quantum lower bounds by quantum arguments

Cited in

(8)

• Quantum-access-secure message authentication via blind-unforgeability
• On exact quantum query complexity
• Quantum and classical tradeoffs
• BQP and the polynomial hierarchy
• The polynomial degree of recursive Fourier sampling
• A stochastic calculus approach to the oracle separation of \(\mathsf{BQP}\) and \(\mathsf{PH} \)
• Oracle separation of BQP and PH
• Oracle Separation of BQP and PH

This page was built for publication: Quantum lower bound for recursive Fourier sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522430)