zbMATH — the first resource for mathematics

On the complexity of unitary transformations. (English. Russian original) Zbl 1088.68609
Discrete Math. Appl. 13, No. 6, 601-606 (2003); translation from Diskretn. Mat. 15, No. 4, 113-118 (2003).
Summary: In this paper, we suggest a method to derive lower bounds for the complexity of nonbranching programs whose elementary operations are unitary transformations over two complex numbers. This method provides us with estimates of the form \(\Omega(n \log n)\) for unitary operators \(\mathbb C^n\to\mathbb C^n\), in particular, for the Fourier and Walsh transformations. For \(n = 2^k\) we find precise values of the complexity of those transformations.
68Q25 Analysis of algorithms and problem complexity
68N01 General topics in the theory of software
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI
[1] J. E. Savage, The Complexity of Computing. Wiley, New York, 1976. · Zbl 0391.68025
[2] A. M. Steane, Quantum computing. Rept. Prog. Phys. (1998) 61, 117-173.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.