The quantum query complexity of AC^0
From MaRDI portal
Publication:2906797
Recommendations
- A lower bound on the quantum query complexity of read-once functions
- Quantum Query Complexity of Boolean Functions with Small On-Sets
- Quantum query complexity of almost all functions with fixed on-set size
- Quantum lower bounds by polynomials
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
Cited in
(18)- A lower bound on the quantum query complexity of read-once functions
- The power of various real-valued quantum queries
- Quantum query complexity of almost all functions with fixed on-set size
- scientific article; zbMATH DE number 1919505 (Why is no real title available?)
- The power of asymmetry in constant-depth circuits
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
- Approximate Degree in Classical and Quantum Computing
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
- Algorithmic Polynomials
- The polynomial method strikes back: tight quantum query bounds via dual polynomials
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Algorithms and Computation
- Quantum algorithms and approximating polynomials for composed functions with shared inputs
- The large-error approximate degree of \(\mathrm{AC}^0\)
- scientific article; zbMATH DE number 7716601 (Why is no real title available?)
- Quantum lower bounds by sample-to-query lifting
- Quantum complexity of the approximation for the classes \({\mathcal B}(W^r_p([0,1]^d))\) and \({\mathcal B}(H^r_p([0,1]^d))\)
- Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
This page was built for publication: The quantum query complexity of \(\mathrm{AC}^0\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2906797)
