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
- John Preskill
- Andrew M. Childs
- Alexei Y. Kitaev
- Michael Mueger
- J. Alicea
- M. B. Hastings
- Zhenghan Wang
- Eric C. Rowell
In Computational Mathematics
- Michael Mueger
- John Preskill
- M. B. Hastings
- Zhenghan Wang
- Eric C. Rowell
- Jennifer M. Franko
- Alexei Y. Kitaev
- Matthew Fisher
In Computational Theory and Mathematics
- Andrew M. Childs
- Michael Mueger
- John Preskill
- M. B. Hastings
- Zhenghan Wang
- Eric C. Rowell
- Jennifer M. Franko
- Alexei Y. Kitaev
Citations in the corpus
- Topological Entanglement Entropy in Chern-Simons Theories and Quantum Hall Fluids (2008, background): “where di are the quantum dimensions of the quasiparticles (labelled by i) of the excitation spectrum associated with this phase, and D is the effective quantum dimension.[15]”
- Tensor categories: a selective guided tour (2008, methodology): “We close with the hypothetical application of modular categories to topological quantum computing [274].”
- Universal topological quantum computation from a superconductor/Abelian quantum Hall heterostructure (2013, background): “coveted, however, because they provide a route to faulttolerant topological quantum computation [14–18].”
- Robustness of adiabatic quantum computation (2001, background): “The fact that adiabatic evolution incorporates a kind of intrinsic fault tolerance has also been noted in [9–14].”
- Quantum computing and the entanglement frontier (2012, background): “39,52,53 Quantum information, stored in the exponentially large fusion Hilbert space of n anyons, is well protected if the temperature is low compared to the energy gap (to prevent unwanted thermal production of anyon pairs) and if the anyons are kept far apart from one another (to prevent unwanted…”
- Non-Abelian statistics and topological quantum information processing in 1D wire networks (2010, methodology): “(3) The transformation of the degenerate ground states under exchange (up to an overall non-universal phase) can be deduced solely by understanding how the Majorana operators transform.”
- Non-Abelian Anyons and Interferometry (2007, neutral): “[79, 80, 81, 82, 83, 84, 85].”
- Generalized trace and modified dimension functions on ribbon categories (2010, background): “These in turn give 3-manifold invariants [49], and provides connections to physics [56, 57] and quantum computing [21, 22].”
- Locality in Quantum Systems (2010, background): “This property, that local operators are close to a multiple of the identity matrix when projected into the ground state sector was identified in the Hall effect[13] and in other topologically ordered states[14].”
- Anyons in an exactly solved model and beyond (2005, background): “A nice elementary introduction can be found in Preskill’s lecture notes on quantum computation [81], but more detail is needed for our purposes.”
- Extraspecial 2-groups and images of braid group representations (2005, methodology): “Certain representations of the braid groups have been proposed as the fractional statistics of anyons [15], and used in the topological models for quantum computing [4].”