Quantum Property Testing for Bounded-Degree Graphs
From MaRDI portal
Publication:3088108
DOI10.1007/978-3-642-22935-0_31zbMath1247.68093arXiv1012.3174OpenAlexW3101738067MaRDI QIDQ3088108
Yi-Kai Liu, Andrew M. Childs, 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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Quantum property testing of group solvability
- Testing the expansion of a graph
- A sublinear bipartiteness tester for bounded degree graphs
- Quantum algorithms for learning and testing juntas
- BQP and the polynomial hierarchy
- New Results on Quantum Property Testing
- On Testing Expansion in Bounded-Degree Graphs
- Property testing and its connection to learning and approximation
- Quantum Walk Based Search Algorithms
- Quantum Property Testing
- Quantum lower bound for the collision problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Simple Constructions of Almost k-wise Independent Random Variables
- On the Power of Quantum Computation
- Quantum Algorithms for Element Distinctness
- Quantum Algorithms for the Triangle Problem
- Quantum lower bounds by polynomials
- Quantum Walk Algorithm for Element Distinctness
- Quantum Query Complexity of Some Graph Problems
- Quantum lower bounds by quantum arguments
- Property testing in bounded degree graphs
This page was built for publication: Quantum Property Testing for Bounded-Degree Graphs
