Efficient quantum circuits for arbitrary sparse unitaries

Stephen P. Jordan and Pawel Wocjan
Phys. Rev. A 80, 062301 – Published 1 December 2009

Abstract

Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus, we obtain a simple unified proof that these models are all contained in BQP. Furthermore, our general method for implementing sparse unitaries simplifies several existing quantum algorithms.

  • Received 21 April 2009

DOI:https://doi.org/10.1103/PhysRevA.80.062301

©2009 American Physical Society

Authors & Affiliations

Stephen P. Jordan1 and Pawel Wocjan2

  • 1Institute for Quantum Information, Caltech, Pasadena, California 91125, USA
  • 2School of Electrical Engineering and Computer Science, University of Central Florida, Orlando, Florida 32816, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 80, Iss. 6 — December 2009

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×