On the public citation graph
Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
0 signed · 126 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/rsa.3240060108openalex-snapshot
On the Monte carlo boolean decision tree complexity of read‐once formulae
inferredcites →https://doi.org/10.1007/s00037-006-0212-7openalex-snapshot
THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS
inferredcites →https://doi.org/10.1016/0020-0190(94)90093-0openalex-snapshot
Size-depth tradeoffs for Boolean formulae
inferredcites →https://doi.org/10.1016/0304-3975(85)90210-5openalex-snapshot
Lower bounds on probabilistic linear decision trees
inferredcites →https://doi.org/10.1016/j.jcss.2003.07.007openalex-snapshot
Learning DNF in time 2Õ(n1/3)
inferredcites →https://doi.org/10.1016/j.jcss.2003.11.002openalex-snapshot
Learning intersections and thresholds of halfspaces
inferredcites →https://doi.org/10.1016/j.jcss.2004.02.002openalex-snapshot
A lower bound on the quantum query complexity of read-once functions
inferredcites →https://doi.org/10.1016/j.jcss.2005.06.006openalex-snapshot
Polynomial degree vs. quantum query complexity
inferredcites →https://doi.org/10.1103/physrevlett.79.325openalex-snapshot
Quantum Mechanics Helps in Searching for a Needle in a Haystack
inferredcites →https://doi.org/10.1137/s0097539792232586openalex-snapshot
Size-Depth Tradeoffs for Algebraic Formulas
inferredcites →https://doi.org/10.1145/502090.502097openalex-snapshot
Quantum lower bounds by polynomials
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/aisy.202200232openalex-snapshot
A New Type of Classical Logic Circuit with Exponential Speedup
inferred← citeshttps://doi.org/10.1002/qute.202300251openalex-snapshot
Quantum Combinational Logics and their Realizations with Circuits
inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_585openalex-snapshot
Quadtrees and Morton Indexing
inferred← citeshttps://doi.org/10.1007/978-3-030-19311-9_13openalex-snapshot
Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs
inferred← citeshttps://doi.org/10.1007/978-3-319-09704-6_1openalex-snapshot
Recent Developments in Quantum Algorithms and Complexity
inferred← citeshttps://doi.org/10.1007/978-3-319-40578-0_21openalex-snapshot
Generating Reversible Circuits from Higher-Order Functional Programs
inferred← citeshttps://doi.org/10.1007/978-3-642-15155-2_1openalex-snapshot
New Developments in Quantum Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-33090-2_18openalex-snapshot
Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
inferred← citeshttps://doi.org/10.1007/978-3-642-33090-2_30openalex-snapshot
The Quantum Query Complexity of Read-Many Formulas
inferred← citeshttps://doi.org/10.1007/978-3-642-38986-3_10openalex-snapshot
An Introduction to Quantum Programming in Quipper
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_10openalex-snapshot
Time-Efficient Quantum Walks for 3-Distinctness
inferred← citeshttps://doi.org/10.1007/978-3-642-54429-3_6openalex-snapshot
Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_22openalex-snapshot
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1007/s00037-013-0066-8openalex-snapshot
A strong direct product theorem for quantum query complexity
inferred← citeshttps://doi.org/10.1007/s00037-016-0134-yopenalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1007/s00037-016-0139-6openalex-snapshot
Quantum Query Complexity of Almost All Functions with Fixed On-set Size
inferred← citeshttps://doi.org/10.1007/s00220-009-0930-1openalex-snapshot
On the Relationship Between Continuous- and Discrete-Time Quantum Walk
inferred← citeshttps://doi.org/10.1007/s00224-009-9219-1openalex-snapshot
Quantum Search with Variable Times
inferred← citeshttps://doi.org/10.1007/s11047-019-09762-6openalex-snapshot
An overview of quantum cellular automata
inferred← citeshttps://doi.org/10.1007/s11128-015-1215-6openalex-snapshot
Quantum walk on the line through potential barriers
inferred← citeshttps://doi.org/10.1007/s11128-017-1667-yopenalex-snapshot
Equivalence of Szegedy’s and coined quantum walks
inferred← citeshttps://doi.org/10.1007/s11128-023-03910-9openalex-snapshot
Quantum bounds for 2D-grid and Dyck language
inferred← citeshttps://doi.org/10.1007/s11128-025-04736-3openalex-snapshot
Robustness of quantum random walk search with multi-phase matching
inferred← citeshttps://doi.org/10.1007/s11424-019-9008-0openalex-snapshot
Quantum Algorithm Design: Techniques and Applications
inferred← citeshttps://doi.org/10.1016/j.ic.2014.12.003openalex-snapshot
Dual lower bounds for approximate degree and Markov–Bernstein inequalities
inferred← citeshttps://doi.org/10.1016/j.laa.2025.02.005openalex-snapshot
Quantum state transfer in graphs with tails
inferred← citeshttps://doi.org/10.1016/j.parco.2014.12.001openalex-snapshot
ScaffCC: Scalable compilation and analysis of quantum programs
inferred← citeshttps://doi.org/10.1016/j.rinp.2023.106327openalex-snapshot
Reducing number of gates in quantum random walk search algorithm via modification of coin operators
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.02.005openalex-snapshot
A stronger LP bound for formula size lower bounds via clique constraints
inferred← citeshttps://doi.org/10.1017/fms.2017.2openalex-snapshot
EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
inferred← citeshttps://doi.org/10.1038/nature23459openalex-snapshot
Programming languages and compiler design for realistic quantum hardware
inferred← citeshttps://doi.org/10.1038/npjqi.2015.23openalex-snapshot
Quantum algorithms: an overview
inferred← citeshttps://doi.org/10.1038/s41598-019-47535-4openalex-snapshot
From curved spacetime to spacetime-dependent local unitaries over the honeycomb and triangular Quantum Walks
inferred← citeshttps://doi.org/10.1088/1751-8113/49/45/455301openalex-snapshot
Doubling the success of quantum walk search using internal-state measurements
inferred← citeshttps://doi.org/10.1103/physreva.100.032308openalex-snapshot
Automated distribution of quantum circuits via hypergraph partitioning
inferred← citeshttps://doi.org/10.1103/physreva.101.062324openalex-snapshot
Quantum walks in weak electric fields and Bloch oscillations
inferred← citeshttps://doi.org/10.1103/physreva.102.042211openalex-snapshot
Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions
inferred← citeshttps://doi.org/10.1103/physreva.109.022412openalex-snapshot
Two methods for breaking down a quantum algorithm
inferred← citeshttps://doi.org/10.1103/physreva.110.062412openalex-snapshot
Quadratic quantum speedup for perceptron training
inferred← citeshttps://doi.org/10.1103/physreva.84.062302openalex-snapshot
Single-qubit unitary gates by graph scattering
inferred← citeshttps://doi.org/10.1103/physreva.97.042131openalex-snapshot
Discrete spacetime, quantum walks, and relativistic wave equations
inferred← citeshttps://doi.org/10.1103/physreva.97.062111openalex-snapshot
Dirac equation as a quantum walk over the honeycomb and triangular lattices
inferred← citeshttps://doi.org/10.1103/physreva.99.032301openalex-snapshot
Quantum walk search on the complete bipartite graph
inferred← citeshttps://doi.org/10.1103/physrevlett.102.180501openalex-snapshot
Universal Computation by Quantum Walk
inferred← citeshttps://doi.org/10.1103/physrevlett.124.180501openalex-snapshot
Grover Search as a Naturally Occurring Phenomenon
inferred← citeshttps://doi.org/10.1103/physrevlett.125.160502openalex-snapshot
Integrated Quantum-Walk Structure and NAND Tree on a Photonic Chip
inferred← citeshttps://doi.org/10.1103/revmodphys.82.1openalex-snapshot
Quantum algorithms for algebraic problems
inferred← citeshttps://doi.org/10.1109/ccc.2012.17openalex-snapshot
A Strong Direct Product Theorem for Quantum Query Complexity
inferred← citeshttps://doi.org/10.1109/ccc.2014.39openalex-snapshot
Fourier Concentration from Shrinkage
inferred← citeshttps://doi.org/10.1109/focs.2011.75openalex-snapshot
Quantum Query Complexity of State Conversion
inferred← citeshttps://doi.org/10.1109/focs.2014.65openalex-snapshot
Shrinkage of De Morgan Formulae by Spectral Techniques
inferred← citeshttps://doi.org/10.1109/focs.2016.57openalex-snapshot
Polynomial Representations of Threshold Functions and Algorithmic Applications
inferred← citeshttps://doi.org/10.1109/focs.2017.10openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC^0
inferred← citeshttps://doi.org/10.1109/icnc.2011.6022357openalex-snapshot
Quantum versus classical query complexity of relation
inferred← citeshttps://doi.org/10.1109/tit.2023.3287556openalex-snapshot
How to Sample From the Limiting Distribution of a Continuous-Time Quantum Walk
inferred← citeshttps://doi.org/10.1134/s1995080223020191openalex-snapshot
Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications
inferred← citeshttps://doi.org/10.1137/100792640openalex-snapshot
Span Programs are Equivalent to Quantum Query Algorithms
inferred← citeshttps://doi.org/10.1137/15m1015704openalex-snapshot
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/16m1064477openalex-snapshot
The Power of Asymmetry in Constant-Depth Circuits
inferred← citeshttps://doi.org/10.1137/17m1161737openalex-snapshot
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
inferred← citeshttps://doi.org/10.1137/20m1312459openalex-snapshot
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
inferred← citeshttps://doi.org/10.1142/s0219749913500597openalex-snapshot
Explicit relation between all lower bound techniques for quantum query complexity
inferred← citeshttps://doi.org/10.1142/s0219749923500302openalex-snapshot
Optimizing the walk coin in the quantum random walk search algorithm
inferred← citeshttps://doi.org/10.1145/2141938.2141939openalex-snapshot
Exact Quantum Algorithms for the Leader Election Problem
inferred← citeshttps://doi.org/10.1145/2213977.2214044openalex-snapshot
Making polynomials robust to noise
inferred← citeshttps://doi.org/10.1145/2488608.2488630openalex-snapshot
Average-case lower bounds for formula size
inferred← citeshttps://doi.org/10.1145/2591796.2591854openalex-snapshot
Exponential improvement in precision for simulating sparse Hamiltonians
inferred← citeshttps://doi.org/10.1145/2694344.2694357openalex-snapshot
Compiler Management of Communication and Parallelism for Quantum Computation
inferred← citeshttps://doi.org/10.1145/3055399.3055444openalex-snapshot
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
inferred← citeshttps://doi.org/10.1145/3055399.3055472openalex-snapshot
Formula lower bounds via the quantum method
inferred← citeshttps://doi.org/10.1145/3123939.3123940openalex-snapshot
Taming the instruction bandwidth of quantum computers via hardware-managed error correction
inferred← citeshttps://doi.org/10.1145/3470863openalex-snapshot
Sign-rank Can Increase under Intersection
inferred← citeshttps://doi.org/10.1145/3519935.3520000openalex-snapshot
The approximate degree of DNF and CNF formulas
inferred← citeshttps://doi.org/10.1145/3571225openalex-snapshot
Qunity: A Unified Language for Quantum and Classical Computing
inferred← citeshttps://doi.org/10.1145/3649811openalex-snapshot
Quantum Control Machine: The Limits of Control Flow in Quantum Programming
inferred← citeshttps://doi.org/10.1145/3656397openalex-snapshot
The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
inferred← citeshttps://doi.org/10.22323/1.427.0175openalex-snapshot
Studying the robustness of quantum random walk search on Hypercube against phase errors in the traversing coin by semi-empirical methods
inferred← citeshttps://doi.org/10.22331/q-2021-09-16-543openalex-snapshot
Quantum algorithms and approximating polynomials for composed functions with shared inputs
inferred← citeshttps://doi.org/10.22331/q-2024-08-23-1444openalex-snapshot
Taming Quantum Time Complexity
inferred← citeshttps://doi.org/10.22331/q-2026-03-23-2039openalex-snapshot
Space-Efficient Quantum Error Reduction without log Factors
inferred← citeshttps://doi.org/10.26421/qic12.3-4-10openalex-snapshot
Limit theorems for the discrete-time quantum walk on a graph with joined half lines
inferred← citeshttps://doi.org/10.26421/qic16.11-12-5openalex-snapshot
Optimal universal quantum cloning: asymmetries and fidelity measures
inferred← citeshttps://doi.org/10.3233/978-1-60750-547-1-115openalex-snapshot
Quantum algorithms for formula evaluation
inferred← citeshttps://doi.org/10.3390/a16030150openalex-snapshot
A Machine Learning Study of High Robustness Quantum Walk Search Algorithm with Qudit Householder Coins
inferred← citeshttps://doi.org/10.3390/sym12010128openalex-snapshot
Dynamical Triangulation Induced by Quantum Walk
inferred← citeshttps://doi.org/10.34133/research.0480openalex-snapshot
Quantum 2-Player Games and Realizations with Circuits
inferred← citeshttps://doi.org/10.4230/lipics.fscd.2018.3openalex-snapshot
Algebraic and Logical Methods in Quantum Computation
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2010.145openalex-snapshot
New Results on Quantum Property Testing
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.67openalex-snapshot
Small Circuits Imply Efficient Arthur-Merlin Protocols
inferred← citeshttps://doi.org/10.48550/arxiv.0908.2468openalex-snapshot
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
inferred← citeshttps://doi.org/10.48550/arxiv.1402.3858openalex-snapshot
Applications of the Adversary Method in Quantum Query Algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1412.0625openalex-snapshot
Quipper: Concrete Resource Estimation in Quantum Algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.1904.12956openalex-snapshot
An overview of Quantum Cellular Automata
inferred← citeshttps://doi.org/10.48550/arxiv.2105.08020openalex-snapshot
Optimizing the walk coin in the quantum random walk search algorithm through machine learning
inferred← citeshttps://doi.org/10.48550/arxiv.2304.15000openalex-snapshot
Quantum Control Machine: The Limits of Control Flow in Quantum Programming
inferred← citeshttps://doi.org/10.5555/2133036.2133079openalex-snapshot
Faster quantum algorithm for evaluating game trees
inferred← citeshttps://doi.org/10.70675/8d7024f3z592fz4cb1z9f10z46474a4e0721openalex-snapshot
Quantum walks : background geometry and gauge invariance
inferred← citeshttps://doi.org/10.7916/d80v8m04openalex-snapshot
Contributions to Information-Based Complexity and to Quantum Computing
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.