[121879] in cryptography@c2.net mail archive
Doubts about efficiency of Shor's factoring algorithm in quantum
daemon@ATHENA.MIT.EDU (Charles McElwain)
Mon Apr 28 17:40:30 2008
Date: Mon, 28 Apr 2008 16:24:55 -0400
From: Charles McElwain <charlesmcelwain1@verizon.net>
To: cryptography@metzdowd.com
In case you missed this, since it appeared in the quantum physics
section; but is relevant to quantum cryptography (or, cryptography on
quantum computers.)
The argument here is that Shor's factoring algorithm is dependent on
the Quantum Fourier Transform, which is sensitive to errors in
quantum input states, and these errors are not capable of being
suppressed by (current) quantum error correcting codes.
Most saliently, 1) these errors destroy the polynomial scaling of
Shor's algorithm, and 2) for those not familiar with the QM terms,
"decoherence" is roughly equivalent to "reduces to classical (i.e.,
non-quantum) state behavior".
Follow-ups on this line of research will be interesting for the
evaluation of any impact of quantum computers on cryptography, and
even generally, since the decoherence behavior would tend to make
quantum computers approximate improving classical computers.
From the Physics pre-print server arXiv, quantum physics section:
http://arxiv.org/abs/0804.3076
Abstract:
>Operator Imprecision and Scaling of Shor's Algorithm
>Authors: C. Ray Hill, George F. Viamontes
>(Submitted on 18 Apr 2008)
>
> Abstract: Shor's algorithm (SA) is a quantum algorithm for
>factoring integers. Since SA has polynomial complexity while the
>best classical factoring algorithms are sub-exponential, SA is cited
>as evidence that quantum computers are more powerful than classical
>computers. SA is critically dependent on the Quantum Fourier
>Transform (QFT) and it is known that the QFT is sensitive to errors
>in the quantum state input to it. In this paper, we show that the
>polynomial scaling of SA is destroyed by input errors to the QFT
>part of the algorithm. We also show that Quantum Error Correcting
>Codes (QECC) are not capable of suppressing errors due to operator
>imprecision and that propagation of operator precision errors is
>sufficient to severely degrade the effectiveness of SA. Additionally
>we show that operator imprecision in the error correction circuit
>for the Calderbank-Shor-Steane QECC is mathematically equivalent to
>decoherence on every physical qubit in a register. We conclude that,
>because of the effect of operator precision errors, it is likely
>that physically realizable quantum computers will be capable of
>factoring integers no more efficiently than classical computers.
Concluding Remarks:
>Quantum error correction is capable of reliably suppressing
>single-qubit errors due to environmental disturbances or operator
>precision errors. However, operator imprecision errors propagate
>and grow during the course of a quantum computation and have an
>important impact on the efficiency of the computation. In
>particular, we have shown that operator precision errors break the
>polynomial scaling of Shor's algorithm and conclude that, in the
>presence of operator precision errors, Shor's algorithm is no more
>efficient than classical algorithms for factoring integers. To
>demonstrate how operator precision errors propagate in practice, we
>proved that the error correction circuit for the CSS QECC is
>mathematically equivalent to applying decoherence on each physical
>quibit in a logical qubit register. We then used simulation to show
>that this accumulated error on eqch qubit causes the probability of
>error in a CSS QECC register to increase linearly with the number of
>gates applied.
>
>It is natural to ask whether these results have wider implications
>about the power of quantum computers relative to classical
>computers. While the results presented in this paper do not answer
>this question definitively, it is important to note the singular
>stature of Shor's algorithm as the only quantum algorithm that
>appears to solve a classically intractable problem. The fact that
>Shor's algorithm is not more efficient than classical algorithms
>removes the only strong evidence for the superior computational
>power of quantum computers relative to classical computers.
--
| || ||| || ||| || ||| || ||| || ||| || ||| || |||
Charles McElwain
33 Vernon Street
Somerville, MA 02145
617-628-5542 (home)
617-501-1591 (cell)
charlesmcelwain1@verizon.net
| || ||| || ||| || ||| || ||| || ||| || ||| || |||
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
