4 papers
Theory of Quantum Computing and Communication
Lance Fortnow
A workshop sponsored by NSF C-CR and organized by the Center for Discrete Math and Theoretical Computer Science (DIMACS) was held at Elmsford, New York, January 17-18, 2002 where w…
Quantum Property Testing
H. Buhrman, L. Fortnow, I. Newman +1
A language L has a property tester if there exists a probabilistic algorithm that given an input x only asks a small number of bits of x and distinguishes the cases as to whether x…
One Complexity Theorist's View of Quantum Computing
Lance Fortnow
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or th…
Complexity limitations on quantum computation
Lance Fortnow, John D. Rogers
We use the powerful tools of counting complexity and generic oracles to help understand the limitations of the complexity of quantum computation. We show several results for the pr…