Poly-Locality in Quantum Computing

By Michael H. Freedman. Foundations of Computational Mathematics, 2000

789 citations recorded by the source corpus.

A polynomial depth quantum circuit affects, by definition, a poly-local unitary transformation of a tensor product state space. It is a reasonable belief [Fe], [L], [FKW] that, at a fine scale, these are precisely the transformations which will be available from physics to solve computational problems. The poly-locality of a discrete Fourier transform on cyclic groups is at the heart of Shor's factoring algorithm. We describe a class of poly-local transformations, which include the discrete orthogonal wavelet transforms, in the hope that these may be helpful in constructing new quantum algorithms. We also observe that even a rather mild violation of poly-locality leads to a model without one-way functions, giving further evidence that poly-locality is an essential concept.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/dacdcd3e8020b4121b13c98d43f11f9a3d8c377b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. John Preskill
  2. Andrew M. Childs
  3. Alexei Y. Kitaev
  4. Michael Mueger
  5. J. Alicea
  6. M. B. Hastings
  7. Zhenghan Wang
  8. Eric C. Rowell

In Computational Mathematics

  1. Michael Mueger
  2. John Preskill
  3. M. B. Hastings
  4. Zhenghan Wang
  5. Eric C. Rowell
  6. Jennifer M. Franko
  7. Alexei Y. Kitaev
  8. Matthew Fisher

In Computational Theory and Mathematics

  1. Andrew M. Childs
  2. Michael Mueger
  3. John Preskill
  4. M. B. Hastings
  5. Zhenghan Wang
  6. Eric C. Rowell
  7. Jennifer M. Franko
  8. Alexei Y. Kitaev

Citations in the corpus