0000000000350189

AUTHOR

Andrew M. Childs

showing 6 related works from this author

Quantum property testing for bounded-degree graphs

2010

We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph s…

FOS: Computer and information sciencesQuantum PhysicsComputer Science - Computational ComplexityComputerSystemsOrganization_MISCELLANEOUSTheoryofComputation_GENERALFOS: Physical sciencesComputational Complexity (cs.CC)Quantum 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

Time-Efficient Quantum Walks for 3-Distinctness

2013

We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.

Discrete mathematicsMatching (graph theory)0102 computer and information sciencesExtension (predicate logic)01 natural sciencesUpper and lower boundsTildeCombinatorics010201 computation theory & mathematics0103 physical sciencesQuantum algorithmQuantum walkConnection (algebraic framework)010306 general physicsTime complexityMathematics
researchProduct

Quantum Property Testing for Bounded-Degree Graphs

2011

We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph s…

Property testingDiscrete mathematicsSpeedupTheoryofComputation_GENERAL0102 computer and information sciences16. Peace & justice01 natural sciencesUpper and lower boundsExponential function010201 computation theory & mathematicsComputerSystemsOrganization_MISCELLANEOUSBounded function0103 physical sciencesQuantum algorithmAlgebraic number010306 general physicsQuantumMathematics
researchProduct

The quantum query complexity of certification

2009

We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

FOS: Computer and information sciencesDiscrete mathematicsQuantum Physics0209 industrial biotechnologyNuclear and High Energy PhysicsQuantum queryComputer scienceDirect sumFOS: Physical sciencesGeneral Physics and AstronomyStatistical and Nonlinear Physics0102 computer and information sciences02 engineering and technologyCertificationComputational Complexity (cs.CC)Certificate01 natural sciencesTheoretical Computer ScienceComputer Science - Computational Complexity020901 industrial engineering & automationComputational Theory and Mathematics010201 computation theory & mathematicsQuantum Physics (quant-ph)QuantumMathematical PhysicsQuantum Information and Computation
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