Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with decision tree):
TR03-005 | 28th December 2002
Scott Aaronson

Quantum Certificate Complexity

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 ... more >>>

TR03-057 | 21st July 2003
Scott Aaronson

Lower Bounds for Local Search by Quantum Arguments

The problem of finding a local minimum of a black-box function is central
for understanding local search as well as quantum adiabatic algorithms.
For functions on the Boolean hypercube {0,1}^n, we show a lower bound of
Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to
solve this ... more >>>

ISSN 1433-8092 | Imprint