603 citations · 1.6k across the 72 of their papers we have counts for
18 papers · 1 filter
An Efficient Quantum Factoring Algorithm
Oded Regev
We show that -bit integers can be factorized by independently running a quantum circuit with gates for times, and then using polynomial-time cl…
Quantum XOR Games
Oded Regev, Thomas Vidick
We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. W…
Impossibility of a Quantum Speed-up with a Faulty Oracle
Oded Regev, Liron Schiff
We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this c…
Bell Violations through Independent Bases Games
Oded Regev
In a recent paper, Junge and Palazuelos presented two two-player games exhibiting interesting properties. In their first game, entangled players can perform notably better than cla…
Near-Optimal and Explicit Bell Inequality Violations
Harry Buhrman, Oded Regev, Giannicola Scarpa +1
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called "Bell inequality violations." We give t…
No Strong Parallel Repetition with Entangled and Non-signaling Provers
Julia Kempe, Oded Regev
We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the \emph{parallel repetition question}: If the game is played $…