77 citations · 461 across the 23 of their papers we have counts for
4 papers · 2 filters
An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
We provide an elementary proof of the quantum adiabatic theorem.
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
Oded Regev
In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-pol…
The Complexity of the Local Hamiltonian Problem
Julia Kempe, Alexei Kitaev, Oded Regev
The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for…
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Dorit Aharonov, Wim van Dam, Julia Kempe +3
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient ad…