6533b85efe1ef96bd12c06f7
RESEARCH PRODUCT
The quantum query complexity of certification
Andris AmbainisFrançois Le GallSeiichiro TaniAndrew M. Childssubject
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 Physicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-03-06 | Quantum Information and Computation |