ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > FORMULA EVALUATION:
Reports tagged with Formula evaluation:
TR10-110 | 14th July 2010
Ben Reichardt

Span programs and quantum query algorithms

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>>




ISSN 1433-8092 | Imprint