REVIEW 2 cited by
Quantum Computation and Decision Trees
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Quantum Computation and Decision Trees
read the original abstract
Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node n levels from the root. We devise a quantum mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level n in time polynomial in n, then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in n, but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.
Forward citations
Cited by 2 Pith papers
-
A Quantum Approximate Optimization Algorithm
A p-layer alternating-operator ansatz on n qubits yields approximation ratios that increase with p, achieving ≥0.6924 for MaxCut on 3-regular graphs at p=1 and approaching 1 in the p→∞ adiabatic limit.
-
Emergence of Krylov complexity through quantum walks: An exploration of the quantum origins of complexity
Reducing a graph walk to distance-layers reproduces Krylov/spread complexity, yielding analytic finite-q SYK Lanczos coefficients and hypercube complexity D sin²(t/D), with faster saturation than classical-walk circuits.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.