Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing.

We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state |x⟩ that is proportional to the solution of the system of linear equations Ax[over →]=b[over →]. The time complexities of our algorithms are O(κ^{2}log(κ)/ε) and O(κlog(κ)/ε), where κ is the condition number of A and ε is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of A, the projector onto the initial state |b⟩, and single-qubit Pauli operators.

Simulating Hamiltonian dynamics with a truncated Taylor series.

We describe a simple, efficient method for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. Our method can simulate the time evolution of a wide variety of physical systems. As in another recent algorithm, the cost of our method depends only logarithmically on the inverse of the desired precision, which is optimal.

Condensation of anyons in frustrated quantum magnets.

We derive the exact ground space of a family of spin-1/2 Heisenberg chains with uniaxial exchange anisotropy (XXZ) and interactions between nearest and next-nearest-neighbor spins. The Hamiltonian family, H(eff)(Q), is parametrized by a single variable Q. By using a generalized Jordan-Wigner transformation that maps spins into anyons, we show that the exact ground states of H(eff)(Q) correspond to a condensation of anyons with a statistical phase φ=-4Q.

Quantum speedup by quantum annealing.

We study the glued-trees problem from A. M. Childs, R.

Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space.

We consider the manifold of all quantum many-body states that can be generated by arbitrary time-dependent local Hamiltonians in a time that scales polynomially in the system size, and show that it occupies an exponentially small volume in Hilbert space. This implies that the overwhelming majority of states in Hilbert space are not physical as they can only be produced after an exponentially long time. We establish this fact by making use of a time-dependent generalization of the Suzuki-Trotter expansion, followed by a well-known counting argument.

Efficient quantum state tomography.

Quantum state tomography--deducing quantum states from measured data--is the gold standard for verification and benchmarking of quantum devices. It has been realized in systems with few components, but for larger systems it becomes unfeasible because the number of measurements and the amount of computation required to process them grows exponentially in the system size. Here, we present two tomography schemes that scale much more favourably than direct tomography with system size.

Efficient solvability of Hamiltonians and limits on the power of some quantum computational models.

One way to specify a model of quantum computing is to give a set of control Hamiltonians acting on a quantum state space whose initial state and final measurement are specified in terms of the Hamiltonians. We formalize such models and show that they can be simulated classically in a time polynomial in the dimension of the Lie algebra generated by the Hamiltonians and logarithmic in the dimension of the state space. This leads to a definition of Lie-algebraic "generalized mean-field Hamiltonians.

A subsystem-independent generalization of entanglement.

We present a generalization of entanglement based on the idea that entanglement is relative to a distinguished subspace of observables rather than a distinguished subsystem decomposition. A pure quantum state is entangled relative to such a subspace if its expectations are a proper mixture of those of other states. Many information-theoretic aspects of entanglement can be extended to this observable-based setting, suggesting new ways of measuring and classifying multipartite entanglement.