Quantum property testing for bounded-degree graphs

DOI10.1007/978-3-642-22935-0_31MaRDI QIDQ3088108zbMATH OpenOpenAlexFDO

Authors Andrew M. Childs, Yi-Kai Liu, Andris Ambainis

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.3174

zbMATH Keywords

bipartiteness testingexpansion testingproperty testingquantum computingquery complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: 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 structure.

Recommendations

• New results on quantum property testing
• Quantum query complexity of minor-closed graph properties
• Quantum query complexity of minor-closed graph properties
• scientific article; zbMATH DE number 1559556
• Property testing in bounded degree graphs

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A sublinear bipartiteness tester for bounded degree graphs
• BQP and the polynomial hierarchy
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 5485493 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• New results on quantum property testing
• On testable properties in bounded degree graphs
• On testing expansion in bounded-degree graphs
• On the Power of Quantum Computation
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Quantum Algorithms for Element Distinctness
• Quantum algorithms for learning and testing juntas
• Quantum algorithms for testing properties of distributions
• Quantum Algorithms for the Triangle Problem
• Quantum lower bound for the collision problem
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum Property Testing
• Quantum query complexity of minor-closed graph properties
• Quantum Query Complexity of Some Graph Problems
• Quantum Walk Algorithm for Element Distinctness
• Quantum Walk Based Search Algorithms
• Simple Constructions of Almost k-wise Independent Random Variables
• Testing the expansion of a graph
• The need for structure in quantum speedups

Cited in

(10)

• New results on quantum property testing
• Self-Testing Graph States
• Quantum Property Testing
• Solving Lyapunov equation by quantum algorithm
• Quantum walk sampling by growing seed sets
• Symmetries, graph properties, and quantum speedups
• (Quantum) complexity of testing signed graph clusterability
• Parameterized quantum query algorithms for graph problems
• Quantum property testing in sparse directed graphs
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems

This page was built for publication: Quantum property testing for bounded-degree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088108)