Poly-locality in quantum computing
<|reference_start|>Poly-locality in quantum computing: 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.<|reference_end|>
@article{freedman2000poly-locality,
    title={Poly-locality in quantum computing},
    author={Michael H. Freedman},
    journal={arXiv preprint arXiv:quant-ph/0001077},
    year={2000},
    archivePrefix={arXiv},
    eprint={quant-ph/0001077},
    primaryClass={quant-ph cs.NA}
}