Quantum property testing

A language <i>L</i> has a property tester if there exists a probabilistic algorithm that given an input <i>x</i> only asks a small number of bits of <i>x</i> and distinguishes the cases as to whether <i>x</i> is in <i>L</i> and <i>x</i> has large Hamming distance from all <i>y</i> in <i>L</i>. We define a similar notion of quantum property testing and show that there exist languages with quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.

• Publication year

  2002

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2002-01-25

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1137/S0097539704442416arXiv quant-ph/0201117
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• Testing graphs for colorability properties *

  2005cited by this paper
• THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING

  2004cited by this paper
• Testing subgraphs in directed graphs

  2003cited by this paper
• Testing Juntas

  2002cited by this paper
• Property Testing in Bounded Degree Graphs

  2002cited by this paper
• Testing of matrix properties

  2001cited by this paper
• Testing graphs for colorable properties

  2001cited by this paper
• Testing subgraphs in large graphs

  2001cited by this paper
• Three theorems regarding testing graph properties

  2001cited by this paper
• Efficient Testing of Large Graphs

  2000cited by this paper
• An improved quantum Fourier transform algorithm and applications

  2000cited by this paper
• Testing of clustering

  2000cited by this paper
• Property Testing

  2000cited by this paper
• Testing the diameter of graphs

  1999cited by this paper
• Regular languages are testable with a constant number of queries

  1999cited by this paper
• Spot-checkers

  1998cited by this paper
• The Probabilistic Method

  1998cited by this paper
• Quantum cryptography with imperfect apparatus

  1998cited by this paper
• Quantum lower bounds by polynomials

  1998cited by this paper
• An exact quantum polynomial-time algorithm for Simon's problem

  1997cited by this paper
• Strengths and Weaknesses of Quantum Computing

  1997influential reference
• Combinatorial property testing (a survey)

  1997cited by this paper
• Property testing and its connection to learning and approximation

  1996cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• A fast quantum mechanical algorithm for database search

  1996cited by this paper
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

  1995cited by this paper
• On the power of quantum computation

  1994influential reference
• Quantum complexity theory

  1993influential reference
• A mathematical theory of self-checking, self-testing and self-correcting programs

  1991cited by this paper
• A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem

  1985cited by this paper
• Probabilistic computations: Toward a unified measure of complexity

  1977cited by this paper
• private communication

  1969cited by this paper

• Quantum Algorithms for Approximate Graph Isomorphism Testing

  2026cites this paper
• Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

  2025cites this paper
• Efficient witnessing and testing of magic in mixed quantum states

  2025cites this paper
• The Knowledge Complexity of Quantum Problems

  2025cites this paper
• Pseudorandom density matrices

  2024cites this paper
• Lower Bounds for Unitary Property Testing with Proofs and Advice

  2024cites this paper
• Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language

  2024cites this paper
• Hypothesis testing of symmetry in quantum dynamics

  2024cites this paper
• Testing classical properties from quantum data

  2024cites this paper
• Quantum property testing in sparse directed graphs

  2024cites this paper
• Classical simulation of one-query quantum distinguishers

  2023cites this paper
• (Quantum) complexity of testing signed graph clusterability

  2023cites this paper
• Pseudorandom unitaries are neither real nor sparse nor noise-robust

  2023cites this paper
• On quantum versus classical query complexity

  2021cites this paper
• Quantum Proofs of Proximity

  2021cites this paper
• Research Statement

  2021cites this paper
• Testing Boolean Functions Properties

  2021cites this paper
• How Close is your Function to Depending on a Small Number of its Inputs?

  2021cites this paper
• An optimal separation of randomized and Quantum query complexity

  2020cites this paper
• How symmetric is too symmetric for large quantum speedups?

  2020cites this paper
• Quantum and classical query complexities for generalized Deutsch–Jozsa problems

  2020cites this paper
• k-forrelation optimally separates Quantum and classical query complexity

  2020cites this paper
• Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving

  2019cites this paper
• Query complexity of generalized Simon's problem

  2019cites this paper
• Towards Optimal Separations between Quantum and Randomized Query Complexities

  2019cites this paper
• Almost tight bound on the query complexity of generalized Simon's problem

  2019cites this paper
• Schur–Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations

  2017cites this paper
• Testing Hereditary Properties of Sequences

  2017cites this paper
• Testing and Searching Pattern Avoiding Sequences

  2017cites this paper
• Application of Grover’s algorithm to check non-resiliency of a Boolean function

  2016cites this paper
• Sequential measurements, disturbance and property testing

  2016cites this paper
• Separations in Communication Complexity Using Cheat Sheets and Information Complexity

  2016cites this paper
• Sculpting Quantum Speedups

  2015cites this paper
• Quantum Pattern Matching Fast on Average

  2014cites this paper
• Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

  2014cites this paper
• Multipartite entanglement in XOR games

  2013cites this paper
• A Survey of Quantum Property Testing

  2013influential citation
• Query-efficient computation in property testing and learning theory

  2012cites this paper
• Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure

  2011cites this paper
• Testing permutation properties through subpermutations

  2011cites this paper
• An efficient test for product states

  2010cites this paper
• J an 2 01 0 An efficient test for product states

  2010cites this paper
• Quantum Property Testing for Bounded-Degree Graphs

  2010cites this paper
• Testing Juntas: A Brief Survey

  2010cites this paper
• Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization

  2010cites this paper
• Property testing and parameter testing for permutations

  2010cites this paper
• An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games

  2010cites this paper
• New Results on Quantum Property Testing

  2010influential citation
• On Finding Sensitivity of Quantum and Classical Gates

  2009cites this paper
• Testing Fourier Dimensionality and Sparsity

  2009cites this paper
• BQP and the polynomial hierarchy

  2009cites this paper
• The Need for Structure in Quantum Speedups

  2009cites this paper
• Quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs ( preliminary version )

  2009cites this paper
• Quantum boolean functions

  2008cites this paper
• Quantum Algorithms

  2008cites this paper
• UvA-DARE (Digital Academic Repository) Quantum property testing

  2008cites this paper
• Quantum Property Testing of Group Solvability

  2007cites this paper
• Quantum Algorithms for Learning and Testing Juntas

  2007cites this paper
• Quantum Property Testing for Solvable Groups

  2006cites this paper
• Advances in quantum computational learning theory

  2006cites this paper
• Self-testing of Quantum Circuits

  2005cites this paper
• Tolerant versus intolerant testing for Boolean properties

  2005influential citation
• Quantum weakly nondeterministic communication complexity

  2005influential citation
• Efficient testing of groups

  2005cites this paper
• On the Complexity of Quantum Languages

  2004cites this paper
• Quantum query: complexity and distributed computing

  2003cites this paper
• Quantum Testers for Hidden Group Properties

  2002influential citation
• Abstract combinatorial programs and efficient property testers

  2002cites this paper
• MIT Open Access Articles Forrelation: A Problem That Optimally Separates Quantum from Classical Computing

  year unknowncites this paper