0000000000354167

AUTHOR

Ben W. Reichardt

showing 4 related works from this author

Span programs and quantum algorithms for st-connectivity and claw detection

2012

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…

Quantum PhysicsFOS: Physical sciencesQuantum Physics (quant-ph)
researchProduct

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

Discrete mathematicsQuantum t-designComputational complexity theoryGeneral Computer ScienceGeneral MathematicsSpectrum (functional analysis)Value (computer science)0102 computer and information sciencesTree (graph theory)01 natural sciencesCombinatoricsTree (descriptive set theory)Discrete time and continuous time010201 computation theory & mathematics0103 physical sciencesQuantum operationQuantum phase estimation algorithmQuantum Fourier transformQuantum walkQuantum algorithm010306 general physicsMathematicsQuantum computerSIAM Journal on Computing
researchProduct

Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection

2012

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…

Clawst-connectivitybusiness.industryA* search algorithm0102 computer and information sciences01 natural sciencesLogarithmic spacelaw.inventionCombinatorics010201 computation theory & mathematicslaw0103 physical sciencesQuantum algorithmAdjacency matrix010306 general physicsbusinessQuantumMathematicsSubdivision
researchProduct

Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions

2007

For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

CombinatoricsDiscrete mathematicsComputational complexity theoryOpen problemExistential quantificationQuantum algorithmQuantum walkComputational geometryUpper and lower boundsQuantum computerMathematics48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
researchProduct