zbMATH — the first resource for mathematics

Poly-locality in quantum computing. (English) Zbl 1075.81507
Summary: A polynomial depth quantum circuit affects, by definition, a poly-local unitary transformation of a tensor product state space. It is a reasonable belief 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.

81P68 Quantum computation
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
65T60 Numerical methods for wavelets
Full Text: DOI