131 citations · 249 across the 4 of their papers we have counts for
9 papers · 1 filter
A Lattice Problem in Quantum NP
Dorit Aharonov, Oded Regev
We consider coGapSVP_\sqrt{n}, a gap version of the shortest vector in a lattice problem. This problem is known to be in AM\cap coNP but is not known to be in NP or in MA. We prove…
A Simple Proof that Toffoli and Hadamard are Quantum Universal
Dorit Aharonov
Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It sho…
Adiabatic Quantum State Generation and Statistical Zero Knowledge
Dorit Aharonov, Amnon Ta-Shma
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum sta…
Quantum NP - A Survey
Dorit Aharonov, Tomer Naveh
We describe Kitaev's result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3-SAT, namely local H…
Quantum Bit Escrow
Dorit Aharonov, Amnon Ta-Shma, Umesh Vazirani +1
Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We in…
Fault-Tolerant Quantum Computation With Constant Error Rate
Dorit Aharonov, Michael Ben-Or
This paper proves the threshold result, which asserts that quantum computation can be made robust against errors and inaccuracies, when the error rate, , is smaller than a const…