Quantum Property Testing
From MaRDI portal
Publication:3532569
DOI10.1137/S0097539704442416zbMath1225.68088MaRDI QIDQ3532569
Ilan Newman, Hein Rohrig, Harry Buhrman, Lance J. Fortnow
Publication date: 28 October 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Randomized algorithms (68W20)
Related Items
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Application of Grover's algorithm to check non-resiliency of a Boolean function ⋮ An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Quantum weakly nondeterministic communication complexity ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Testing permutation properties through subpermutations ⋮ Schur-Weyl duality for the Clifford group with applications: property testing, a robust Hudson theorem, and de Finetti representations ⋮ Query complexity of generalized Simon's problem ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Testing Boolean Functions Properties