Showing quant-phShow all
3 papers · 1 filter
quant-ph2005
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, Mario Szegedy
We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has b…
quant-ph2003
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
Sophie Laplante, Frederic Magniez
We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmo…
quant-ph2000
Quantum Kolmogorov Complexity
Andre Berthiaume, Wim van Dam, Sophie Laplante
In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can…