Name
Abstract | ||
|---|---|---|
Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation R0(f)=O(Q2(f)2Q0(f)logn) for total f, where R0, Q2, and Q0 are zero-error randomized, bounded-error quantum, and zero-error quantum query complexities respectively. Finally we give asymptotic gaps between the measures, including a total f for which C(f) is superquadratic in QC(f), and a symmetric partial f for which QC(f)=O(1) yet Q2(f)=Ω(n/logn). |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/j.jcss.2007.06.020 | Journal of Computer and System Sciences |
Keywords | Field | DocType |
Quantum computing,Query complexity,Black box,Decision tree,Block sensitivity,Adversary method,Merlin–Arthur,Boolean function | Quantum complexity theory,Karp–Lipton theorem,Boolean function,Discrete mathematics,Quantum,Combinatorics,Boolean circuit,Circuit complexity,Parity function,Theoretical computer science,Mathematics,Certificate | Journal |
Volume | Issue | ISSN |
74 | 3 | 0022-0000 |
Citations | PageRank | References |
0 | 0.34 | 16 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Scott Aaronson | 1 | 1016 | 77.48 |