77 citations · 168 across the 10 of their papers we have counts for
4 papers · 1 filter
An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
We provide an elementary proof of the quantum adiabatic theorem.
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Elchanan Mossel, Ryan O'Donnell, Oded Regev +2
In this paper we study non-interactive correlation distillation (NICD), a generalization of the study of noise sensitivity of boolean functions. We extend the model to NICD on tree…
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…