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)
[EMAIL PROTECTED]
| || ||| || ||| || ||| || ||| || ||| || ||| || |||
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
