{\huge Quantum Repetition}

Aram Harrow and Gil Kalai debate ``Conjecture 1''

\vspace{.5in}

William Wootters and Wojciech Zurek were office-mates in 1979 as graduate students at U.T. Austin in John Wheeler's group. A paper by Nick Herbert of the Fundamental Fysiks Group crossed their desks with an idea toward harnessing quantum mechanics for faster-than-light communication. Fascinated though skeptical, they realized the scheme made an implicit assumption. It assumed the ability to make a perfect copy of an arbitrary quantum state $latex {a\ket{0} + b\ket{1}}&fg=000000$, i.e., a qubit---except Wootters didn't coin that term until 1995. Independently of Dennis Dieks in 1982, they proved that only special---not general---qubit states can be cloned. The name ``No-Cloning Theorem'' was supplied by Wheeler.

Today we continue the debate between Gil Kalai and Aram Harrow on scalable quantum computing, focusing on how ideas about repetition impact Gil's ``Conjecture 1'' from the series' initial post.

The debate was expected to conclude last spring, but ideas and material to sustain it have developed in preprints with refutations, new queries, copious comments sometimes preceded by private exchanges, and further discussions on the participants' own fora. We note especially that John Preskill has posted a full paper, ``Sufficient condition on noise correlations for scalable quantum computing,'' extending work we previously referenced. Today's post was to be the conclusion, but as it passed 20 \LaTeX pages we declared this part of it a fourth ``round'' instead. We apologize that some of it is necessarily ``entangled'' with the yet-to-appear conclusion, which will follow shortly.

In his first response post, Aram described a classical error-correction test, and then began an approach against Gil's Conjecture 1 using repetition codes. In this post they discuss these two matters further. We first present three different ways of repeating things, the last a thought experiment by Gil that set the initial terms of Aram's analysis. Then comes Aram's detailed modeling and critique of Conjecture 1, followed by a response by Gil. Finally we present Gil's summation on the issue of why classical computers are possible.

Rep-A, Rep-B, and Rep-C

Given an object $latex {q}&fg=000000$, the simplest fault-tolerance idea is to make $latex {n}&fg=000000$ independent copies: $latex {q,q,\dots,q}&fg=000000$. That way if fewer than $latex {n/2}&fg=000000$ of them are corrupted, the majority vote of the others will preserve the original. Let's call this building-block idea Rep-A.

When the object $latex {q}&fg=000000$ represents a probability distribution (classical or quantum) then things become more involved. If $latex {q}&fg=000000$ is a classical biased coin $latex {p\mathbf{0}+(1-p)\mathbf{1}}&fg=000000$ or a qubit $latex {a\ket{0} + b\ket{1}}&fg=000000$ what does it mean to repeat $latex {q}&fg=000000$? What is the precise object we are repeating? Here, the no-cloning theorem (which also has a classical counterpart) is of some relevance.

One can do Rep-B: Suppose $latex {q}&fg=000000$ is a qubit with unknown value $latex {a\ket{0} + b\ket{1}}&fg=000000$. We can use entanglement to create

$latex \displaystyle \ket{q^{(n)}} = a\ket{0^n} + b\ket{1^n}.&fg=000000$

Nature allows this as a general quantum operation. This idea extends to more complicated classical and quantum error correcting codes.

In Gil's thought experiment $latex {q}&fg=000000$ is a classical biased coin $latex {p\mathbf{0}+(1-p)\mathbf{1}}&fg=000000$. The Rep-C idea is to represent this by $latex {(p\mathbf{0}+(1-p)\mathbf{1})^{\otimes n}}&fg=000000$. The "decoding" of a state of $latex {n}&fg=000000$ bits gives to `1' its expected weight over the $latex {n}&fg=000000$ bits. Aram will subsequently discuss the quantum version.

We will see how these ideas play out in arguments over Gil's Conjecture 1, which was originally stated as follows:

Conjecture 1 (No quantum error-correction): In every implementation of quantum error-correcting codes with one encoded qubit, the probability of not getting the intended qubit is at least some $latex {\delta > 0}&fg=000000$, independently of the number of qubits used for encoding.

Gil: a classical analog of a quantum computer

Aram's analysis of Conjecture 1 builds on this thought experiment offered by Gil. This is an example to show that had we lived in a classical noisy world where the classical analog of Conjecture 1 holds for the noisy microscopic scale, noiseless classical memory and computation were nevertheless possible.

The classical analog of Conjecture 1 (let's call it Conjecture 1$latex {'}&fg=000000$) asserts that when we use Rep-C to encode a classical random bit $latex {p\mathbf{0}+(1-p)\mathbf{1}}&fg=000000$ we get, with a substantial probability that is bounded away from 0, states that decode into codewords of the form $latex {q\mathbf{0}+(1-q)\mathbf{1}}&fg=000000$ where $latex {q}&fg=000000$ is distributed in a neighborhood of $latex {p}&fg=000000$. (Conjecture 1$latex {'}&fg=000000$ is not true in general, but what we see in a minute is that it is not harmful to the repetition code.)

The point is that Rep-C, even under a noise that satisfies Conjecture 1$latex {'}&fg=000000$, allows noiseless classical information and classical computation. For that you represent `0' by $latex {p\mathbf{0} +(1-p)\mathbf{1}}&fg=000000$ when $latex {p}&fg=000000$ is greater than $latex {1/2}&fg=000000$ and `1' by $latex {p\mathbf{0}+(1-p)\mathbf{1}}&fg=000000$ when $latex {p}&fg=000000$ is smaller than $latex {1/2}&fg=000000$.

Aram: Harrow: Conjecture 1 and the repetition code

A central part of Gil's skepticism is his conjecture 1, which essentially asserts that quantum error-correcting codes cannot work as advertised. Here is my restatement of that conjecture.

There exist a universal constant $latex {\delta>0}&fg=000000$ with the following properties. Let $latex {{\cal E}}&fg=000000$ be an encoding map (specifically, a quantum operation) that maps one qubit to $latex {n}&fg=000000$ qubits. Let $latex {|\psi\rangle}&fg=000000$ be a pure single-qubit state (the ``intended state'') and $latex {{\cal P}}&fg=000000$ a procedure that, in the absence of noise, would prepare the state $latex {{\cal E}(|\psi\rangle\langle \psi|)}&fg=000000$. Let $latex {\tilde{\cal P}}&fg=000000$ be the effect of $latex {{\cal P}}&fg=000000$ in the presence of physically realistic noise. Then there exists a distribution $latex {\mu_{{\cal P},\psi}}&fg=000000$ satisfying

$latex \displaystyle \mathbb{E}_{|\tilde{\psi}\rangle \sim \mu_{{\cal P},\psi}} \|\, |\psi\rangle - |\tilde\psi\rangle\| \geq \delta. &fg=000000$

and a noise process $latex {{\cal N}}&fg=000000$ such that $latex {\tilde{\cal P}}&fg=000000$ instead prepares a state close to

$latex \displaystyle {\cal N}\left( \mathbb{E}_{|\tilde{\psi}\rangle \sim \mu_{{\cal P},\psi}} [{\cal E}(|\tilde\psi\rangle \langle\tilde\psi|)] \right). &fg=000000$

There are a number of questions about this conjecture that one might raise:

One consequence of $latex {\cE}&fg=000000$ being a quantum operation is that it commutes with taking the expectation over $latex {|\tilde\psi\rangle}&fg=000000$. If we then define the map $latex {\cN'}&fg=000000$ (which itself could plausibly be a quantum operation, such as depolarizing noise with strength $latex {\delta}&fg=000000$) by

$latex \displaystyle \cN'(|\psi\rangle\langle\psi|):= \mathbb{E}_{|\tilde{\psi}\rangle \sim \mu_{{\cal P},\psi}} |\tilde\psi\rangle \langle\tilde\psi|), &fg=000000$

then the state asserted in Conjecture 1 can be rewritten more simply as

$latex \displaystyle \cN(\cE(\cN'(|\psi\rangle\langle\psi|))).&fg=000000$

By contrast, the conventional/optimistic view is that states of the form $latex {\cN(\cE(|\psi\rangle\langle\psi|))}&fg=000000$ can be prepared, without $latex {\cN'}&fg=000000$. Thus Conjecture 1 is tantamount to asserting that noise will inevitably strike before a state is safely encoded. Of course this would be true if we followed the naive strategy of preparing $latex {|\psi\rangle}&fg=000000$ outside of an error-correcting code, and then performing the encoding map; since we cannot perform this encoding arbitrarily quickly, there will always be a constant amount of noise that occurs before the state is protected. (Note that FT computing, whether classical or quantum, does not use this strategy, which is a point that is overlooked by Robert Alicki's paper quant-ph/0411008.) But Conjecture 1 asserts that the same effect will plague any protocol $latex {\cP}&fg=000000$.

\subsubsection*{Two repetition codes} Let us attempt to apply Conjecture 1 to the simplest code: the $latex {1\rightarrow n}&fg=000000$ repetition code. We have to be careful because in fact there are at least two ways to define the repetition code as a quantum code. The one that I believe makes the most sense is to add $latex {n-1}&fg=000000$ qubits in the $latex {\ket 0}&fg=000000$ state, and perform controlled-NOT gates from the input qubit onto each of the new qubits. This will map

$latex \displaystyle a\ket 0 + b\ket 1 \mapsto a \ket{0^n} + b\ket{1^n},&fg=000000$

where $latex {\ket{0^n} := \ket{0}^{\otimes n}}&fg=000000$ and $latex {\ket{1^n} := \ket{1}^{\otimes n}}&fg=000000$. Extending this to a quantum operation, we obtain

$latex \displaystyle \begin{array}{rcl} &&\cE_{\text{Rep-B}}( a_{00} \ket{0}\bra{0} + a_{01} \ket{0}\bra{1} + a_{10} \ket{1}\bra{0} + a_{11} \ket{1}\bra{1}) \\ &=& a_{00} \ket{0^n}\bra{0^n} + a_{01} \ket{0^n}\bra{1^n} + a_{10} \ket{1^n}\bra{0^n} + a_{11} \ket{1^n}\bra{1^n}. \end{array} &fg=000000$

This ``Rep-B'' idea is only one interpretation of the repetition code. It can correct up to $latex {\frac{n-1}{2}}&fg=000000$ bit-flip errors, but is vulnerable to even a single phase error. (A standard theorem of quantum error correction states that it suffices to consider only these two types of errors.)

The other idea, cloning, is simply to copy the input state $latex {n}&fg=000000$ times, viz.:

$latex \displaystyle \cE_{\text{Rep-C}}(\rho) = \rho^{\otimes n}.&fg=000000$

This cloning map is not used in any FT scheme, classical or quantum, probably because it does not lend itself well to error-correction. For any error-correcting code, we would like a procedure to project a state (i.e. density matrix) onto the linear subspace of valid code states. Operationally this corresponds to measuring whether a (detectable) error has occurred. For Rep-B, this corresponds to checking whether our state is in $latex {\text{span}\{\ket{0^n}, \ket{1^n}\}}&fg=000000$.

For Rep-C, this operation is trivialized: since $latex {\cE_{\text{Rep-C}}(I/2)}&fg=000000$ is the maximally mixed state on $latex {n}&fg=000000$ qubits, then any state is compatible with this. Thus, we can never look at an $latex {n}&fg=000000$-qubit state and say that it is not a valid encoding of some state under Rep-C. This weakness stems in part from the fact that Rep-C is a nonlinear map, while decoding or error-detecting is necessarily linear. As a result, I believe that (contrary to Gil's arguments) Rep-C does not make sense even for classical FT, unless it is redefined until it essentially becomes Rep-B (e.g. the domain is restricted to be the states $latex {\proj 0,\proj 1}&fg=000000$ and it is extended linearly to all states).

It is perhaps worth reviewing here how classical FT computing is workable using Rep-B.

  1. Each logical bit is represented by $latex {n}&fg=000000$ physical bits which are ideally in the state $latex {\cE(\proj 0)}&fg=000000$ or $latex {\cE(\proj 1)}&fg=000000$, but in practice will merely be close (in typical Hamming distance) to these states.
  2. Fresh logical bits are introduced to the computation by initializing blocks of $latex {n}&fg=000000$ physical bits to the state $latex {\cE(\proj 0)}&fg=000000$.
  3. If the computation is randomized, then instead we can initialize a block of $latex {n}&fg=000000$ physical bits to the state $latex {\cE(I/2)}&fg=000000$.
  4. Gates are performed transversally, to minimize the propagation of errors. That is, to store the AND of logical bits $latex {x}&fg=000000$ and $latex {y}&fg=000000$ in a logical bit $latex {z}&fg=000000$, we assume that these bits are stored in physical bits $latex {x_1,\ldots,x_n,y_1,\ldots,y_n,z_1,\ldots,z_n}&fg=000000$, and we then set $latex {z_i = x_i \cdot y_i}&fg=000000$ for each $latex {i}&fg=000000$. In this way, errors will be magnified by at most a constant multiple.
  5. In-between each gate, we will do error correction to attempt to restore each bit to a valid code state. Physically, this is achieved by a bistable flip-flop (in RAM) or a ferromagnetic material (in a hard drive). The former is ``active'' in that it requires a continuous supply of power, while the latter is ``passive'' in that it will correct errors simply by being in contact with a room-temperature thermal bath (and samples of magnetite from the sea floor have demonstrated that this sort of memory can last for at least millions of years).

(For Rep-C, steps 1, 2 and 4 are the same, but steps 3 and 5 fail.) One not-so-obvious point is that $latex {\cE}&fg=000000$ is never performed. Rather, we develop schemes to directly prepare states such as $latex {\cE(\proj 0)}&fg=000000$.

FT quantum computing works in essentially the same way as the above strategy, except that the repetition code is replaced by a code that can correct a large number of both bit-flip and phase errors.

\subsubsection*{Applying conjecture 1 to the repetition code} What happens if we apply Conjecture 1 to Rep-B? First, observe that after encoding, the states become extremely sensitive to phase errors, since a single phase error on any qubit will affect the phase of the encoded qubit. Thus, outputs of $latex {\cE_{\text{Rep-B}}}&fg=000000$ can effectively be assumed to be classical mixtures of $latex {\proj{0^n}}&fg=000000$ and $latex {\proj{1^n}}&fg=000000$. Indeed, applying $latex {\cN}&fg=000000$ to the output will also ensure this.

But what if we have ``pre-encoding'' noise $latex {\cN'}&fg=000000$ that is, say, a depolarizing channel of strength $latex {\delta}&fg=000000$? Then attempting to prepare $latex {\cE(\proj 0)}&fg=000000$ will inevitably result in a state of the form

$latex \displaystyle (1-\delta)\proj{0^n} + \delta \proj{1^n}.&fg=000000$

This means that if we attempt to initialize a bit in a RAM or a hard drive to a ``0'' state then there will be a probability $latex {\delta}&fg=000000$ that it instead yields ``1''. The situation is even more absurd when one considers other versions of a repetition code. Consider an abacus with beads consisting of $latex {10^{23}}&fg=000000$ atoms, each of which can be either slid to the left or the right. Conjecture 1 would imply that if we attempt to slide a bead on the abacus to the left using our best possible technology, then we will inevitably accidentally place it on the right with probability $latex {\delta}&fg=000000$.

This should be enough to dispose of Conjecture 1. After all, it is stated as applying to all codes. If an exception is built in for Rep-B (which is the key code behind classical computing), then it starts to look rather camel-shaped.

Indeed, the conjecture cannot even be repaired by saying that ``for all $latex {\cE}&fg=000000$, there exists a $latex {\ket{\psi}}&fg=000000$ for which $latex {\cN(\cE(\proj\psi))}&fg=000000$ is hard to prepare.'' Because for the repetition code, preparing the encoded state is simply a matter of flipping a coin with a very precise bias, and then preparing many qubits in a way controlled by this coin flip. Again this is something that could have already been achieved with an abacus.

What about applying Conjecture 1 to Rep-C? This is the situation that Gil discusses when he says that Conjecture 1 is compatible with classical computing. Indeed for Rep-C, noise before encoding behaves pretty much the same way as noise after encoding. So, Conjecture 1 is compatible with $latex {\cE_{\text{Rep-C}}}&fg=000000$. Can we say that if Conjecture 1 doesn't hold for every code, it at least holds for some code? Perhaps, but I don't view Rep-C as particularly representative of error-correcting codes, because if we use any code other than the repetition code, then only the ``-B'' framework makes sense. Moreover, given that Rep-C cannot distinguish between pre-encoding noise and i.i.d. post-encoding noise, it seems hard to use it as evidence in favor of Conjecture 1.

I believe that Conjecture 1 is likely to fail for most interesting maps $latex {\cE}&fg=000000$. In general, if a system has a two-dimensional topologically protected subspace, then mixing within this subspace is exponentially suppressed. Like Conjecture C, I believe it is too broad. But there may well be more specific classes of states that noise effectively prevents us from creating.

Gil: Conjectures 1 and Aram's classical error correction test

A review of Conjectures 1

Conjecture 1 asserts that encoded quantum qubits are noisy. What do we mean by a noiseless encoded qubit? If $latex {f(\psi)}&fg=000000$ is an encoding of $latex {\psi}&fg=000000$ with $latex {n}&fg=000000$ qubits we require that $latex {\psi}&fg=000000$ can be determined from $latex {{\cal N}\left (f(\psi )\right )}&fg=000000$ up to an error that we cannot distinguish from zero in probability that we cannot distinguish from 1. Quantum error correction achieves this (for every $latex {\psi}&fg=000000$) when we let the number of qubits used in the encoding grows. (For this formulation you may need to rely also on the Kitaev-Solovay theorem.) Conjecture 1 asserts that this is not possible.

\subsubsection *{The case of the repetition code}

In the context of quantum fault tolerance and the threshold theorem the only repetition code which is relevant is Rep-B. I always regarded Conjecture 1 for the repetition code as obviously true. Indeed, it is correct that when $latex {\psi=|0\rangle}&fg=000000$ or $latex {\psi=|1\rangle}&fg=000000$ $latex {{\cal N}(f(\psi))}&fg=000000$ determines $latex {\psi}&fg=000000$ uniquely, but for any other value of $latex {\psi}&fg=000000$ there is a whole (one-dimensional) "cloud" of states that we cannot distinguish from $latex {\psi}&fg=000000$. So the repetition code supports having a stable ground state and a stable excited state but does not support noiseless superposition of these states. This example indeed shows (and I thank Aram for clarifying it) that when I say "the probability" in Conjecture 1 you have either to consider the worst case $latex {\psi}&fg=000000$ or to take also $latex {\psi}&fg=000000$ at random in computing the probability. Aram claims that Conjecture 1 is violated by Rep-B for every $latex {\psi}&fg=000000$. Let's look at that.

\subsubsection*{Aram's formalization of Conjecture 1}

A large part of my work with many backtracks and difficulties was to translate conjectures from English to mathematics. This is not a simple matter at all. (This is an opportunity to mention Greg Kuperberg who found various loopholes in some of my early attempts.) So it feels nice to see Aram trying to formalize Conjecture 1, and overall, Aram mathematical formulation of Conjecture 1 is reasonable except that there is one term which is left in English. "... $latex {\tilde{\cal P}}&fg=000000$ instead prepares a state close to $latex {{\cal N}\left( \mathbb{E}_{|\tilde{\psi}\rangle \sim \mu_{{\cal P},\psi}} [{\cal E}(|\tilde\psi\rangle \langle\tilde\psi|)] \right).}&fg=000000$ What does "prepare instead" mean? The way I would formalize this English part, which agrees with what Conjecture 1 is all about, is that with probability larger than $latex {\delta}&fg=000000$ the encoding for $latex {\psi}&fg=000000$ after the noise and the encoding of $latex {\mu_{P,\psi}}&fg=000000$ after the noise cannot be distinguished. This is not Aram's interpretation. Aram's interpretation of Conjecture 1 is simply incorrect. If I understand correctly what Aram says he would regard also the trivial code which encodes every $latex {\psi}&fg=000000$ by $latex {|0^n\rangle}&fg=000000$ as a counterexample to Conjecture 1. Again, this is incorrect.

Let me response to Aram's challenge and try myself to formulate Conjecture 1 (it can either stand alone or complement the missing part in Aram's formulation).

Conjecture 1 (no quantum error-correction): Denote by $latex {d}&fg=000000$ the trace-distance. There exists $latex {\delta > 0}&fg=000000$ with the following property. Consider a realistic device which encode a single qubit with $latex {n}&fg=000000$ qubits. Suppose that $latex {F(\psi)}&fg=000000$ denotes the encoded state of the single-qubit state $latex {\psi}&fg=000000$. Then there are two states $latex {\psi}&fg=000000$ and $latex {\phi}&fg=000000$ so that $latex {d(\psi,\phi) >\delta}&fg=000000$ and

$latex \displaystyle d(F(\psi),F(\phi))<1-\delta .&fg=000000$

\subsubsection *{Conjecture 2}

The strong principle of noise (Conjecture 2) which is more general than Conjecture 1 asserts that you cannot find a noiseless quantum evolution as a subsystem of a realistic noisy quantum evolution. Both of these conjectures require some formal description but are interesting and lead to fruitful insights even without such a description. Let me mention Aram's second thought experiment which was a very original attempt at a counterexample for conjecture 2. Rather than trying to hide a noiseless evolution inside a large noisy one, Aram suggested to enlarge a noisy evolution into a larger noiseless system. Looking carefully at this suggestion the conclusion (see this comment by Aram concluding a long discussion) was that it cannot work.

Conjectures 1 and 2 do not describe noise models but can be seen as requirements from yet hypothetical realistic noise model. In the next post, I will describe a Hamiltonian noise model which is meant to express formally the idea of ``no quantum FT'' and to support Conjectures 1-4. We will also mention a suggestion regarding the rate of noise which is relevant to both Conjectures 1 and 2. When we talk about "what is a qubit" we assume that we can manipulate the state of the qubit in a fairly general way and we need to relate the rate of noise with the qubit's evolution.

Aram's classical error-correction test

Why do we have (essentially) noiseless classical memory? Why are classical computers possible? This is indeed the heart of the matter. Here is my point of view:

We start with the strong principle of noise that says that you cannot find a noiseless quantum evolution as a subsystem of a realistic noisy quantum evolution. A special case of this general principle is Conjecture 1 which asserts that qubits must be noisy; For any encoded qubit we have a substantial mixture of the intended codeword with a ``cloud'' of unintended codewords.

How does Conjecture 1 allows for noiseless bits? We now need the following repetition principle:

Let $latex {D_1}&fg=000000$ and $latex {D_2}&fg=000000$ be two distinct probability distributions. Represent '0' by a sequence of $latex {n}&fg=000000$ samples from $latex {D_1}&fg=000000$ and '1' by a sequence of $latex {n}&fg=000000$ independent draws from $latex {D_2}&fg=000000$. If $latex {n}&fg=000000$ is large enough then '0' and '1' are noiseless bits. (This is true even if in the presence of additional noise of various kind and even if the independence assumption on the samples is relaxed in various ways.)

It follows that a device able to create large samples from two distinct probability distributions enables noiseless bits, and and when we (or nature) control such a device then noiseless classical computation is possible.

\subsection *{Aram's analogy with 2-SAT and 3-SAT}

Aram started his 3-posts reply with the following analogy: ``If you want to prove that 3-SAT requires exponential time, then you need an argument that somehow doesn't apply to 2-SAT or XOR-SAT. If you want to prove that the permanent requires super-polynomial circuits, you need an argument that doesn't apply to the determinant. And if you want to disprove fault-tolerant quantum computing, you need an argument that doesn't also refute fault-tolerant classical computing.''

This is correct. Proving that 3-SAT needs exponential time requires an argument that does not apply to 2-SAT and XOR-SAT. Today, after many years, we still do not have such an argument. But this does not mean that we should believe that 3-SAT behaves like 2-SAT. Indeed, while the proof is a still far, we have strong reasons to believe that 3-SAT is hard; a world where 3-SAT is easy presents a very different reality than ours. Similarly, proving that fault-tolerance quantum computing is impossible will require more experimental efforts and theoretical progress. But the fundamental differences, as those described in the last post, between a world with fault-tolerant quantum computing and our present reality give fair reasons to believe and certainly to explore the possibility that quantum fault tolerance is not possible.

The distinction between classical and quantum error-correction is a major issue whether you are skeptical about the feasibility of universal quantum computers or not. In my opinion, the repetition principle in a reality which obeys Conjectures 1 and 2 draws an appealing picture for the distinction between classical error-correction and quantum error-correction. Aram proposed a different explanation which relies on both the repetition code and on the difficulty to find in 3D quantum forms of passive memories and some commentators offered other explanations. I find these explanations less satisfactory.

\subsection * {How to model the memory of digital computers: Is Rep-B or Rep-C more appropriate?}

Here is an interesting question that came up as a byproduct of my discussion above with Aram on the repetition code. Using Aram's terminology the question is "Does the microscopic structure of digital memory better described by Rep-B or by something like Rep-C?" When we think about the memory of a digital computer as a vast array of electrons with up spins and down spins where '0' is represented by (say) 0.01 fraction of up spins and '1' is represented by a 0.99 fraction of up spins then the Rep-B description suggests a very tight fluctuation for the number of up spins. The Rep-C description is more relaxed and allows the fraction to fluctuate in an entire interval like [0.009,0.012]. Of course, the digital memory implement a repetition of a specific state $latex {\psi}&fg=000000$ and not of a general state, so the question is if we should consider the state of the digital computer repressenting '0' as $latex {|0^n\rangle}&fg=000000$ subject to small independent noise or as $latex {|\psi\rangle^{\otimes n}}&fg=000000$ where $latex {\psi}&fg=000000$ is some fixed state near $latex {|0\rangle}&fg=000000$ which is itself subject to noise.

There is a more general issue here. I expect that in various stochastic/Hamiltonian models for noise we witness Gaussian concentration of the number of errors. Of course, such a concentration is not required for quantum error-correction. I tend regard this feature as unrealistic and therefore such models, in my opinion, leave out a crucial aspect of noise which may or may not allow fault tolerance. See this comment. It will be interesting to understand whether Preskill's recent assumptions on correlation imply concentration for the number of errors.

Open Problems

Do the assumptions on correlated noise in the models by Aharonov-Kitaev-Preskill and Preskill imply concentration of the number of errors?

Is the microscopic structure of digital memory better described by Rep-B or by Rep-C? Do the fluctuations in the number of up spins in digital computers memory behave like the square root of the number of spins? Does the no-cloning theorem have any bearing on these questions?