Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
From MaRDI portal
Publication:3068642
DOI10.1137/080712167zbMath1207.68151OpenAlexW2031374990MaRDI QIDQ3068642
Shengyu Zhang, Andrew M. Childs, Ben W. Reichardt, Robert Špalek, Andris Ambainis
Publication date: 17 January 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080712167
Related Items (33)
Quantum walk on the line through potential barriers ⋮ Challenges of adiabatic quantum evaluation of NAND trees ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ Hardness Amplification and the Approximate Degree of Constant-Depth Circuits ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Generating Reversible Circuits from Higher-Order Functional Programs ⋮ Breaking the Minsky--Papert Barrier for Constant-Depth Circuits ⋮ Quantum query complexity of almost all functions with fixed on-set size ⋮ The Power of Asymmetry in Constant-Depth Circuits ⋮ A strong direct product theorem for quantum query complexity ⋮ Quantum algorithm for dynamic programming approach for DAGs and applications ⋮ Optimizing the walk coin in the quantum random walk search algorithm ⋮ Quantum bounds for 2D-grid and Dyck language ⋮ On the relationship between continuous- and discrete-time quantum walk ⋮ An overview of quantum cellular automata ⋮ Equivalence of Szegedy's and coined quantum walks ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ ⋮ EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS ⋮ Algorithmic Polynomials ⋮ Quantum algorithm design: techniques and applications ⋮ The hardest halfspace ⋮ Fourier concentration from shrinkage ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Random Walks – New Method for Designing Quantum Algorithms ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum Algorithms for Evaluating Min-Max Trees ⋮ Dual lower bounds for approximate degree and Markov-Bernstein inequalities
This page was built for publication: Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
