Subject: Re: Quantum computing practically impossible

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 4 Nov 2020 23:23:32 -0500

The charter for QIRG is talking about using quantum communication channels.
The paper is talking about Shorr's work on error correction which is
relevant to quantum cryptanalysis, an entirely different topic.

It is my understanding of the work on Quantum error correction that it is
correcting errors in the measurement of quantum states rather than trying
to compensate for decoherence so the base assumption of the paper seems to
be off.

There are good reasons to build quantum computers, cryptanalysis ain't one
of them. Not unless we can get a scalable approach like trapped ion to
work. Building bigger and colder fridges is obviously a dead end. I really
don't feel PKI as we know it is threatened at this point, but it is
obviously something we need to keep a very watchful eye on because
deploying new PKI systems has a twenty year time frame.

This is basic research and there is much from the Internet that may help
inform that work. But it is still basic research.

On Sat, Oct 31, 2020 at 8:30 AM Masataka Ohta <
[email-masked]> wrote:

> Let me initiate some *technical* discussion on practical impossibility
> of quantum computing, here, because there is no WG in IETF for it.
>
> QIRG is in IRTF and is chartered for, not against, quantum things.
>
> As is discussed in:
>
>         https://tools.ietf.org/html/draft-ohta-qec-inapplicable-00
>
> though quantum error correction by Shor assumes that, if an entangled
> state is composed as superposition of (exponentially) many unentangled
> terms, all the terms are *IDENTICALLY* disturbed by noise retaining
> their relative coherence, which is obviously impossible. They are
> actually disturbed *DIFFERENTLY*, correction of which is, obviously,
> impossible with constant (not exponentially many, at all) number of
> extra qubits.
>
> As a result, quantum computing, relying on entangled states
> with (exponentially) many unentangled terms, with practical
> size is impossible and PKI is safe against quantum computers.
>
> The draft is 5 pages long and requires mere elementary understanding
> on entanglement.
>
>                                                         Masataka Ohta
>
>

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 5 Nov 2020 01:44:27 -0500

> to compensate for decoherence so the base assumption of the paper seems to

No.  That's not the case.  The scepticism around in principle
scalability of QCs is in fact centered on whether environmental noise
can be corrected in principle or not.  Much has been written about this
by Gil Kalai, who has a long-running debata with Scott Aaronson on this
issue.  Neither side has conceded.  The Google "quantum supremacy"
announcement has given the pro-QC camp some reason for new optimism, but
Gil Kalai is disputing the conclusions of that experiment.

Time will tell who's right.  The devil is in very difficult details of
the noise models that the experts don't agree on.

-- 
    Viktor.

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 5 Nov 2020 17:28:51 +0900

> to compensate for decoherence so the base assumption of the paper seems to

Read the draft and you can find Shor's paper, the first
paper on quantum error correction (reference [1] of the
draft), is titled "Scheme for reducing decoherence in
quantum computer memory".

The idea of Shor was that the measurement will reset randomly
decoherred state to one of a finite set of states. As measurement
result can identify which member of the set the states are
reset by the measurement, the original state can be restored,
which, Shor said, is reduction of decoherence, where reduction
means compensation for single, but not double, qubit errors.

The problem is that if a state is entangled with many unentangled
terms, unless relative coherence between the terms is strictly
retained, which is the impossible assumption of Shor, such
reduction is impossible.

Differently decoherred terms need term specific ways to reduce
decoherence, which is impossible by measuring fixed number of
extra qubits.

> There are good reasons to build quantum computers,

If only it had scaled with quantum error correction.

						Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Thu, 5 Nov 2020 20:11:54 +0900

Viktor Dukhovni wrote:

> issue.  Neither side has conceded.

The point of Gil should be that:

	https://www.quantamagazine.org/gil-kalais-argument-against-quantum-computers-20180207/
	All physical systems are noisy, he argues, and qubits kept
	in highly sensitive “superpositions” will inevitably be
	corrupted by any interaction with the outside world.

should, obviously, be valid.

However, he overlooked a fact that "interaction with the outside
world" is very strong in quantum computers running quantum
algorithms where qubits directly involved in some QEC circuits are
actively entangled with many other qubits outside of the QEC
circuits but, still, in the quantum computers.

> Time will tell who's right.

Now is the time.

 > The devil is in very difficult details of

Not. It's just straight forward.

In my draft, I strictly follow the noise model by Shor that
noises result in local interaction between qubits and their
local environment.

However, though Shor overlooked a fact that local environment
states and resulting error/noise operators are different term
by term if quantum state is entangled represented by superposition
of many unentangled terms, the local environment states and resulting
error/noise operators are different term by term.

In other words, Shor thought entangled states were just as fragile/noisy
as unentangled states, against a well known fact that really entangled
states are a lot more fragile/noisy than unentangled states.

						Masataka Ohta

---

From: Joseph Touch <[email-masked]>
Date: Thu, 5 Nov 2020 07:34:35 -0800

> On Nov 4, 2020, at 10:44 PM, Viktor Dukhovni <[email-masked]> wrote:
> 
> can be corrected in principle or not.

Noise isn’t the only focal point of skepticism; at least one other is full-entanglement scale, which has essentially remained static for decades (8-way recently leaping to 10-way).

Joe

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 5 Nov 2020 14:11:51 -0500

> Gil Kalai is disputing the conclusions of that experiment.

I was trying to avoid wading into that fight. My bigger point was that
particular debate is irrelevant as far as the scope of QIRG goes. My minor
point being that is not the only reason for needing correction. Quantum
computers are interesting in that your results come back in the form of bar
graphs...

As far as I am concerned, Quantum Computing is really the name of a branch
of experimental physics looking to find out if quantum states decohere
independently or obey the Q-rule of 'one down, all down'. And that is an
interesting experiment but not one we know the result of, nor is it
something that we can possibly know through extrapolation of other results.
I am pretty sure we will find that the states do behave as you suggest but
only because every other observation in physics is compatible with the
observed universe being a simulation performed using lazy evaluation but
that is a butter-side-up mode of reasoning.

> the noise models that the experts don't agree on.

Experiment will show who is right - if someone can work out the experiment
to build.

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 6 Nov 2020 05:43:03 +0900

> Experiment will show who is right - if someone can work out the experiment

Wrong.

Read the draft, which says:

    experimental confirmation of
    Shor's quantum error correction should success, as long as the input
    qubit to an error correction circuit is unentangled with other qubits
    outside of the circuit, which is not the case when quantum algorithms
    are run on quantum computers relying on aggressive entanglement
    between qubits.

						Masataka Ohta

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 6 Nov 2020 06:23:39 +0900

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 6 Nov 2020 06:32:52 +0900

Sorry for the previous mail sent before editing.

Joseph Touch wrote:

> Noise isn’t the only focal point of skepticism; at least one other is
> full-entanglement scale, which has essentially remained static for
> decades (8-way recently leaping to 10-way).

It was considered that, once certain accuracy is obtained,
recursive application of quantum error correction can
increase the scale.

But, it is based on wrong assumption that entangled states are
just as noisy/fragile as unentangled ones, though each
unentangled term consisting an entangled state is
disturbed by noise independently, which makes the
state a lot more noisy/fragile than unentangled ones.

					Masataka Ohta

---

From: Joseph Touch <[email-masked]>
Date: Thu, 5 Nov 2020 14:09:04 -0800

> recursive application of quantum error correction can

Regardless, I’m reporting what others are raising as concerns; they’re aware of this.

However, recursive application increases distance, not numbers of entangled parties.

Joe

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 6 Nov 2020 13:24:10 +0900

> However, recursive application increases distance, not numbers of entangled parties.

As noise destroys entangled states, improved SNR by recursive
QEC was expected to increase the number of entangled parties.

						Masataka Ohta

---

From: Rodney Van Meter <[email-masked]>
Date: Fri, 6 Nov 2020 18:24:50 +0900

For people who are mildly interested in the topic of quantum error
correction, we have a short discussion and a Javascript app that shows
some of the basic ideas in our MOOC (which is now free).
https://www.futurelearn.com/courses/intro-to-quantum-computing

For people with serious interest, there are two topics to cover:
decoherence, and quantum error correction.  (We'll leave aside
fault-tolerant execution of algorithms, which requires yet more work.)

My favorite source on decoherence is "Introduction to decoherence and
noise in open quantum systems," by Todd Brun and Daniel Lidar, which
is the opening chapter in the compendium _Quantum Error Correction_
(Cambridge, 2013).  Unfortunately, AFAIK, it's not publicly available
in PDF.  Other sources include John Preskill's lecture notes (which
are freely available) at
http://www.theory.caltech.edu/~preskill/ph219/ph219_2018-19 and many
books on quantum computing, such as the classic Nielsen & Chuang
(Cambridge, 2000).  Be warned that this does take moderately
good linear algebra chops, and if you want to really understand
decoherence, some partial differential equations.

If you want to learn about quantum error correction, my favorite
source is Devitt, Nemoto & Munro, "Quantum Error Correction for
Beginners," arXiv:0905.2794v3 [quant-ph].  Already over a decade old,
but still outstanding.  But "for beginners" assumes you have a decent
quantum background, just nothing on QEC.

-----

Okay, a little on mohta-san's concerns...

There are multiple sources of errors and multiple types.

* bit flip: a symmetric channel, with 0-->1 and 1-->0 errors equally
  likely
* phase flip: ditto, but for a qubit's phase
* amplitude damping: In this mode, 1-->0 errors are more likely than
  0-->1 errors, because the former happens when a photon is emitted
  and thpe latter when a photon is absorbed; moving to the
  lower-energy state is more common.  This is the harder one to
  understand.
  https://en.wikipedia.org/wiki/Amplitude_damping_channel
  http://www.thphys.nuim.ie/staff/jvala/Lecture_12.pdf

We can also talk about various gate errors, and errors in
measurement.  One that particularly worried me is, in fact, one of the
things that Peter Shor simplified away in his first QEC paper: what
happens when the errors on individual qubits aren't independent?

*ALL* of these are handled properly by quantum error correction.  In
fact, they can all be treated as types of memory errors, which
(thankfully) simplifies the math.

This is over-simplified, but QEC consists of several phases:

1. Encoding a logical state
1.5 <<errors happen>>
2. Extracting syndrome information
   a. calculating the syndromes in superposition
   b. measuring the syndrome qubits, which *forces the state into one
      with discrete errors*
3. Using that information to correct the state.

Steps 2 & 3 are repeated over the lifetime of the algorithm execution,
interleaved with the operations that execute logical gates.  (Well, in
codes known as topological codes, surface codes, toric codes and color
codes, that's not quite true.  Those codes also have no classical
equivalent, whereas other codes derive very directly from classical
error correction.)

Step 2a involves quantum operations, and so *adds* errors into the
state, meaning an interesting question is when the error correction
process as a whole *removes* more errors than the extraction adds.
Monroe's group claims to have exceeded that threshold.

Mohta's concern seems to be two-fold; first, that errors aren't
independent, and second, that forcing of the state (actually, a
*partial* collapse of the quantum state) doesn't take you a state
where applying correction works.

As it happens, the first problem worried me enough that I wrote about
it in my Ph.D. thesis.  See Sec. 2.3.5 (p. 55) of
https://arxiv.org/abs/quant-ph/0607065
Fundamentally, coherent noise over a group of qubits (e.g., some
coherent radio noise from outside, or shared dependence on a slightly
incorrect classical oscillator, or something) results in all of
the suppressed *to second order* -- to the *square* of the induced
rotation angle (since it's less than 1.0, that means reducing the
error).

A similar argument applies to the amplitude damping that is the harder
error type mentioned above: the syndrome extraction forces us back to
a state where, *with high probability*, the correction we choose to
apply makes the state better (== closer to the original) rather than
worse.

Some QEC schemes operate by applying multiple recursive levels of the
same (or, possibly, different) encoding schemes.  Yes, that results in
a big growth in resources used, but a) we're only talking about 2 or 3
levels, not some huge number; and b) the errors are actually
suppressed at a rate that exceeds the resource consumption, so it all
works out in the end.  I won't go into the math of that here.

Fundamentally, quantum error correction *works*, and over the course
of 2020-2025, we will see it demonstrated increasingly clearly in
experimental systems.

Barring something really extraordinary, this is all I will have to say
on the topic on ietf@ietf.  People who are interested are welcome to
attend the QIRG meeting (Monday afternoon Bangkok time during IETF)
and ask about this during the open mic.  Since we have other business
to attend to on the already-published agenda, I will defer discussion
of this draft and this topic to the very last thing, but I expect
there will be some time available.

See y'all online in a couple of weeks!

—Rod

---

From: Rodney Van Meter <[email-masked]>
Date: Fri, 6 Nov 2020 18:26:25 +0900

Doh, copy-paste failure, I missed the top of the mail I wrote.  Trying again:

I'm co-chair of QIRG, but speaking as an individual here.

I was planning to let this slip by, since I don't think ietf@ietf is
the right forum for deciding whether or not a minority view on the
effectiveness of quantum computing is correct.  But since we're
here...

I've known mohta-san for several years now, and we've had F2F
discussions of this and relevant topics.  He's asking a good question,
and in fact I had similar ones when I began studying quantum computing
in 2003.  He certainly isn't the first person to ask these questions,
but he doesn't accept the answer that the vast majority of the QC
community does.  Fair enough.  Skepticism is largely healthy, but I
expect that time will prove him wrong.  I would say that his view
diverges enough from the broad understanding of the community that it
does not affect important aspects of the IRTF decision to charter QIRG
and invest some effort (entirely voluntary, of course) of the
IETF/IRTF community in the area.

In fact, I would argue that time has *just recently* shown skeptics to
be wrong.  (Or, to be accurate, "is now showing," since the paper is
apparently still under peer review.)  Chris Monroe's group at UMD
(moving to Duke) in September posted a paper to the arXiv preprint
server claiming that their ion trap can create a fully error-protected
logical qubit, using a scheme known as the 9-qubit Bacon-Shor code.  I
was so excited about this paper that I tweeted, "It's here! The
logical qubit is here!"  There are a few 't's to be dotted and a few
'i's to be crossed before it can be used in practice, but I think this
will stand as a landmark paper.
https://arxiv.org/abs/2009.11482

For 90% of ietf@ietf, that's probably enough; don't feel guilty if you
stop reading right here.  But I'll follow up with some references,
then some specific points about mohta-san's concerns.

-------

-----

—Rod

---

From: Masataka Ohta <[email-masked]>
Date: Fri, 6 Nov 2020 23:04:02 +0900

Rodney Van Meter wrote:

> Other sources include John Preskill's lecture notes (which
> are freely available) at
> http://www.theory.caltech.edu/~preskill/ph219/ph219_2018-19

Nice reference. As is stated in

	http://www.theory.caltech.edu/~preskill/ph229/notes/chap1.pdf

that

	As we have noted, the essential property of quantum
	information that a quantum computer exploits is the
	existence of nonlocal correlations among
	the different parts of a physical system.

"nonlocal correlations among the different parts of a physical system"
generates nonlocal, that is, globally affecting all qubits, noises,
which can not be corrected (when probability that more than half of
qubits (including those used for error correction) are erroneous is
not negligible, error correction is impossible) which is overlooked
by Shor.

He improperly assumed that environment states around qubits are
same between terms consisting entangled states, whereas, entanglement
means the states can be different term by term.

Even though qubits are thermally isolated, if they are entangled,
nonlocal correlations occur between not-really-QEC circuits,
which can not be corrected locally within the circuits.

A complication, as is explained in my draft, is that Shor's model
on noise covers slightly entangled, that is, slightly nonlocal,
cases, but, is not useful against a fact that input qubits to
QEC circuits in quantum computers running quantum algorithms
are aggressively entangled with other qubits outside of the
circuit but still within the computer (seemingly, Gil Kalai
thought about interaction with qubits (or whaterver) totally
outside of the computer, entanglement with which can be
arbitrary small if the computer is thermally isolated from
outside environment).

						Masataka Ohta

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 6 Nov 2020 11:25:09 -0500

Mohta-san,

With all due respect for the fact English is not your first language. I
read what you wrote but was unable to parse it.

My objection to what you wrote is that you are claiming 'proof'. I have a
research degree in experimental particle physics. You certainly do not have
proof for your position at this time.

To be fair, there are claims being made on the pro-QC side which also go
far beyond what has been proved. Witness the large number of
implementations of Shorr's algorithm for factoring that effectively make
use of the factors as an input.

As a designer of cryptographic infrastructures, it is clear that it is
highly unlikely there will be a general purpose quantum computer capable of
breaking X25519 available within one or even two decades. But unlikely is
not the same as proven beyond doubt to be impossible.

* It is therefore prudent to consider means of hardening an infrastructure
so that it is resilient to quantum cryptanalysis.

* The possibility is nowhere near as serious as to demand that we stop
trying to use public key cryptography just in case someone succeeds.

Phill

---

From: Michael Richardson <[email-masked]>
Date: Fri, 06 Nov 2020 17:21:13 -0500

> so that it is resilient to quantum cryptanalysis.

One of critical things that we (the IETF and IoT community) need to do is
show that we have all the tooling required to do Hash-Based Signature
Algorithm updates for SUIT (RFC8778).

A fire-drill in essence.
We don't need to it well, but we need to be able to do that.

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide

---

From: Masataka Ohta <[email-masked]>
Date: Sat, 7 Nov 2020 11:37:08 +0900

Phillip Hallam-Baker wrote:

> Witness the large number of

 > I have a research degree in experimental particle physics.

Then, I hope you can understand my draft does not deny
Shor's algorithm for factoring.

There are two major contributions of Shor for quantum
computing.

One is Shor's algorithm for efficient factoring, which
is not denied by my draft.

The other is quantum error correction, which is denied
by my draft.

Latter was expected to make quantum computers scale.

As a result, we can't construct a quantum computer to
run Shor's factoring algorithm for >1000 (or >100 or,
maybe, even >20) bit numbers.

						Masataka Ohta