2000/01/21 by Michael Freedman, Freedman, Michael H.
Computer Science · Physics and Astronomy · #FOS: Mathematics #FOS: Physical sciences #Numerical Analysis (math.NA) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.quant-ph/0001077
openalex publication_date 2000/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A polynomial depth quantum circuit effects, by definition a poly-local unitary transformation of tensor product state space. It is a physically reasonable belief [Fy][L][FKW] that these are precisely the transformations which will be available from physics to help us solve computational problems. The poly-locality of discrete Fourier transform on cyclic groups is at the heart of Shor's factoring algorithm. We describe a class of poly-local transformations, including all 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.