[Cryptography] Quantum computers will never overcome noise issues?

Allen allenpmd at gmail.com
Fri Feb 16 09:50:39 EST 2018


Interestingly, researchers at Oxford have just reported creating a
quantum gate with a record breaking precision of 99.9%.  My
understanding is that it therefore generates the wrong result with a
probability of 0.001.

   https://phys.org/news/2016-08-record-breaking-logic-gate-important-milestone.html
   http://www.bbc.com/news/science-environment-43065485

I went back and compared this with an estimate of the number of
quantum gates required to break elliptic curve encryption.
Researchers at Microsoft estimate that breaking P-256 would require
2330 qubits and 1.26E11 Toffoli gates.  See Table 2 on page 21 of

   https://arxiv.org/abs/1706.06752

Significantly I think, 1.16E11 of the Toffoli gates would sequential,
meaning the outputs of one gate would feed the inputs of the next.  At
an error rate of 0.001, the probability of error in 1.16E11 sequential
gates would be (1-0.001)^1.16E11 which is essentially 1, i.e., the
results would never be accurate.  In order to get even somewhat
accurate results with so many sequential gates, the error rate needs
to be roughly the same magnitude as the number of sequential gates, in
other words, with 1E11 sequential gates, we would need an error rate
below 1E-11, or roughly "11 nines" of precision.  My guess is that is
well below any noise floor that could be achieved in practice.

Do I understand correctly how the sequential gates and error rates
work?  Comments/corrections/feedback are welcome.  If I did understand
it correctly, then in order to break elliptic curve encryption, we
would need quantum algorithms where the number of sequential gates is
less than the error rate, which I'm guessing might be around 1E4 or
1E5.  I'm guessing there is also may be a tradeoff between the gate
depth and the number of gates and qubits, but it might be exponential,
in other words, you can half the gate depth if you square the number
of gates and qubits.  The relationship between the gate depth and
number of gates and qubits might prove to be a key determinant of
whether elliptic curve encryption can ever be broken using a quantum
computer.  Thoughts?


More information about the cryptography mailing list