Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians (2009)
We present two universal models of quantum computation with a time-independent, frustration-free Hamiltonian. The first construction uses 3-local (qubit) projectors, and the second one requires only...
Fast Amplification of QMA (2009)
Nagaj, Daniel, Wocjan, Pawel, Zhang, Yong
Given a verifier circuit for a problem in QMA, we show how to exponentially amplify the gap between its acceptance probabilities in the `yes' and `no' cases, with a method that is quadratically...
An Efficient Circuit for the Quantum Walk Update Rule (2009)
Chiang, Chen-Fu, Nagaj, Daniel, Wocjan, Pawel
We show how to efficiently implement quantum update rules corresponding to arbitrary sparse classical walks (Markov chains). These rules are required to realize quantum walks as defined by Szegedy....
Quantum Speed-up for Approximating Partition Functions (2008)
Wocjan, Pawel, Chiang, Chen-Fu, Abeyesinghe, Anura, Nagaj, Daniel
We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo Markov Chain method...
Local Hamiltonians in Quantum Computation (2008)
In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show...
Local Hamiltonians in Quantum Computation (2008)
In this thesis, I investigate aspects of local Hamiltonians in quantum computing. First, I focus on the Adiabatic Quantum Computing model, based on evolution with a time dependent Hamiltonian. I show...
Hamiltonian Quantum Cellular Automata in 1D (2008)
We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external...
Local Hamiltonians in quantum computation (2008)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Physics, 2008.
Local Hamiltonians in quantum computation (2008)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Physics, 2008.
The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States (2007)
Nagaj, Daniel, Farhi, Edward, Goldstone, Jeffrey, Shor, Peter, Sylvester, Igor
We give a generalization to an infinite tree geometry of Vidal's infinite time-evolving block decimation (iTEBD) algorithm for simulating an infinite line of quantum spins. We numerically investigate...
A new construction for a QMA complete 3-local Hamiltonian (2006)
We present a new way of encoding a quantum computation into a 3-local Hamiltonian. Our construction is novel in that it does not include any terms that induce legal-illegal clock transitions....
How to Make the Quantum Adiabatic Algorithm Fail (2005)
Farhi, Edward, Goldstone, Jeffrey, Gutmann, Sam, Nagaj, Daniel
The quantum adiabatic algorithm is a Hamiltonian based quantum algorithm designed to find the minimum of a classical cost function whose domain has size N. We show that poor choices for the...
On the Optimality of Quantum Encryption Schemes (2005)
Kerenidis, Iordanis, Nagaj, Daniel
It is well known that n bits of entropy are necessary and sufficient to perfectly encrypt n bits (one-time pad). Even if we allow the encryption to be approximate, the amount of entropy needed...