<p>An interesting analysis of error propagation has been published last february on QIP.
Arxiv version: <a href="https://arxiv.org/abs/1610.05223" rel="nofollow noreferrer">https://arxiv.org/abs/1610.05223</a></p>

<p>Quantum Error Correction (QEC) for state preservation is a major topic in QC. You may find plenty of theoretical and experimental papers on QEC. For example: <a href="http://www.nature.com/nature/journal/v519/n7541/full/nature14270.html" rel="nofollow noreferrer">http://www.nature.com/nature/journal/v519/n7541/full/nature14270.html</a> </p>

CC BY-SA 3.0
2017-05-12T13:13:20.250Z
This looks interesting, but I'm not quite sure how to connect it to my question. I have edited my question to hopefully better reflect what I mean to ask.
Heinrich Apfelmus
CC BY-SA 3.0
2017-05-12T05:28:02.750Z
2017-05-12T06:02:37.953Z
2017-05-12T06:02:37.953Z
Michele Amoretti
<p>It appears that my question about "numerical accuracy" / error correction for qubits is nicely answered in the bible of quantum computation, <a href="http://www.cambridge.org/de/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computation-and-quantum-information-10th-anniversary-edition?format=PB&amp;isbn=9781107002173" rel="nofollow noreferrer">M.A. Nielsen and I.L. Chuang, "Quantum Computation and Quantum Information", Oxford Univ. Press, 2010</a>, chapter 10, in particular section 10.3.1. This book is great, I think that it is both very readable and very thorough!</p>

<p>The key point is the following: Yes, errors may be introduced during the calculation so that the superpositions becomes more and more "inaccurate" in small ways. Then, it may seem very strange that in many papers on error correction in quantum computation, authors often only correct for a few types of errors, in particular <em>bit flip</em> errors ($|0\rangle\leftrightarrow|1\rangle$) and <em>sign flip</em> errors ($|1\rangle\to -|1\rangle$). What about small deviations in superposition coefficients? The answer is: If you correct for the former kind of error, then the latter ones are accounted for as well! (Theorem 10.2 in the book.) The reason is that if you account for bit and sign flip errors, then you automatically account for any <em>linear combination</em> of these errors, which now includes small deviations in the coefficients as well. Hurray!</p>

<p>In general, when thinking about qubits, it is not a good idea focus on the fact that the superposition coefficients can be arbitrary real numbers. Sure, Shor's algorithm requires a fairly precise cancellation of these coefficients. But a better point of view is to think of a qubit as something much closer to a classical bit, which has only two discretes states $0$ and $1$, than to a high precision real number from the interval $[0,1]$. The point is that when we try to <em>physically</em> measure a qubit, we only ever get one of two discrete answers (albeit with interesting probabilities), so it's pretty much discrete.</p>

<p>If we compare analog and quantum computers, then it is fair to say that an analog computer tries to encode as much information as possible in high precisions real numbers, whereas a quantum computer has essentially just discrete bits with a little bit of "quantum extra". Then the key point to the computational power of quantum computers is not that a qubit contains real numbers, but that qubits combine by taking the tensor product of Hilbert spaces ($H_1 \otimes H_2$) whereas analog computers combine by just adding more real numbers, corresponding to the direct sum of vector spaces ($V_1 \oplus V_2$). The "little quantum extras" combine into something useful if we add many of them.</p>

<p>Also note that at the time of this writing, it is totally unclear whether quantum computers are really more powerful than classical computers. As far as I am aware of, there is no "genuine" (no oracles) problem that can be solved efficiently <em>only</em> with a quantum computer, i.e. where we have proof that a classical computer can't do it efficiently. Quantum computers certainly don't solve the $NP = P$ problem.</p>

CC BY-SA 3.0
2017-05-16T13:15:09.767Z
You do not count factoring of large numbers (or any abelian hidden subgroup problem) to be a genuine problem ?
Frédéric Grosshans
CC BY-SA 3.0
2017-05-16T14:29:37.940Z
Nice answer to your own question
Frédéric Grosshans
CC BY-SA 3.0
2017-05-17T08:53:27.100Z
@FrédéricGrosshans I do count factoring of large numbers among the genuine problems, it's just that we have no proof that it can be efficiently solved *only* with a quantum computer. I have edited my answer to reflect that.
Heinrich Apfelmus
CC BY-SA 3.0
2017-07-31T16:12:09.980Z
Recently, there has been a lot of research a set of non-oracle problems, like boson sampling, which are known to be efficiently solvable on quantum computers, but are hard to solve on classical computers, unless the [polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy) collapses to the 3rd level. I don’t know if these problems count as genuine (they are not oracle based, but are totally artificial), or if the separation can be considered proved, since they rely on a conjecture on the PH, but I think it is the best we have know
Frédéric Grosshans
CC BY-SA 3.0
2017-05-14T15:15:46.473Z
2017-05-17T08:54:35.230Z
2017-05-17T08:54:35.230Z
Heinrich Apfelmus
<p>I am new to the topic of quantum computers (though I am very familiar with both quantum and computers, and I have studied Shor's paper about his eponymous algorithm at some point). Still, I have the following question, which pertains to the practical realizability of quantum computers and is probably related to qubit error correction:</p>

<p>To set up the question, note that <em>classical computers</em> are typically built on the principle that information is best encoded <em>digitally</em>, e.g. by two discrete bits <code>0</code> and <code>1</code>. Every now and then, however, somebody claims that <em>analog</em> computing is better, where information is encoded in a continuous quantity $a \in [0,1]$, e.g. a voltage between $0V$ and $1V$. If this quantity were an exact real number, then it is well known that we could solve many problems really fast. However, such schemes do not work in practice, because continuous quantities are always subject to measurement error and do not allow arbitrary precision.</p>

<p><em>Quantum computers</em>, on the other hand, rely on the principle that information is encoded in qubits $|0\rangle$, $|1\rangle$ and <em>arbitrary superpositions</em> thereof, like $0.6|0\rangle + 0.8|1\rangle$. In light of the above remark about analog computers, the appearance of arbitrary precision real numbers in the superposition raises a red flag. Of course, typical models of quantum computation account for this problem by allowing only a fixed (select) set of universal gates (e.g. the Hadamard gate and a few others). Then, the precision required in the coefficients of the superposition need not be larger than the number of gates used in the computation.</p>

<p>However, this still leaves open the question of what happens if we increase the number of gates. Then, the precision needed to represent the coefficients of the superposition will also increase. But due to unavoidable random fluctuations, it seems inevitable to me that an intermediate calculation might use slightly inaccurate results, e.g. one qubit may take the value $0.0447|0\rangle + 0.999|1\rangle$ instead of $1.0|1\rangle$ as desired. Further manipulations with gates may distort the end result drastically.</p>

<blockquote>
  <p>How can I make sure that errors in intermediate qubit results do not propagate?</p>
</blockquote>

<p>The problem I perceive is that the precision per qubit superposition is fixed, and may at some point be too low to accommodate more gates, very similar to the problem of precision of an analog computer.</p>

<p>Apologies if this is a standard question in a misguided disguise, this has probably been answered already. I would appreciate any pointer.</p>

<p>EDIT: Let me try to reformulate my question. Consider the following model of computation: Just like with a quantum computer, each qubit is a superposition $a|0\rangle + b|1\rangle$. However, we now postulate that the computer has only finite precision, i.e. that the superposition coefficients $a$,$b$ must be contained in a <em>discrete set</em> of values, for example $a,b,\in \{0.1,0.2,\dots,1.0\}$. This is equivalent to a "rounding error", where each unitary operation "rounds" the coefficients to the ones from the discrete set of values. Clearly, this model of computation is entirely classical, as each qubit can only take a finite number of superpositions, which we can encode by a classical bit string.</p>

<blockquote>
  <p>How do quantum computers go beyond the "finite precision coefficients" while avoiding the "analog computers with infinite precision are too powerful" problem?</p>
</blockquote>

CC BY-SA 3.0
2017-05-16T14:30:23.703Z
Your question is indeed a standard objection ([#6 in this 2006 lecture by Scott Aaronson](http://www.scottaaronson.com/democritus/lec14.html)) against quantum computers.
Frédéric Grosshans
CC BY-SA 3.0
2018-04-04T00:41:27.113Z
You can ask this question at: https://quantumcomputing.stackexchange.com/ .
Rob
<quantum-computing>
Numerical accuracy of superpositions in quantum computers
Heinrich Apfelmus
# Numerical accuracy of superpositions in quantum computers

(Asked by: username_0 on 2017-05-11)

I am new to the topic of quantum computers (though I am very familiar with both quantum and computers, and I have studied Shor's paper about his eponymous algorithm at some point). Still, I have the following question, which pertains to the practical realizability of quantum computers and is probably related to qubit error correction:

To set up the question, note that *classical computers* are typically built on the principle that information is best encoded *digitally*, e.g. by two discrete bits `0` and `1`. Every now and then, however, somebody claims that *analog* computing is better, where information is encoded in a continuous quantity $a \in [0,1]$, e.g. a voltage between $0V$ and $1V$. If this quantity were an exact real number, then it is well known that we could solve many problems really fast. However, such schemes do not work in practice, because continuous quantities are always subject to measurement error and do not allow arbitrary precision.

*Quantum computers*, on the other hand, rely on the principle that information is encoded in qubits $|0\rangle$, $|1\rangle$ and *arbitrary superpositions* thereof, like $0.6|0\rangle + 0.8|1\rangle$. In light of the above remark about analog computers, the appearance of arbitrary precision real numbers in the superposition raises a red flag. Of course, typical models of quantum computation account for this problem by allowing only a fixed (select) set of universal gates (e.g. the Hadamard gate and a few others). Then, the precision required in the coefficients of the superposition need not be larger than the number of gates used in the computation.

However, this still leaves open the question of what happens if we increase the number of gates. Then, the precision needed to represent the coefficients of the superposition will also increase. But due to unavoidable random fluctuations, it seems inevitable to me that an intermediate calculation might use slightly inaccurate results, e.g. one qubit may take the value $0.0447|0\rangle + 0.999|1\rangle$ instead of $1.0|1\rangle$ as desired. Further manipulations with gates may distort the end result drastically.

> How can I make sure that errors in intermediate qubit results do not propagate?

The problem I perceive is that the precision per qubit superposition is fixed, and may at some point be too low to accommodate more gates, very similar to the problem of precision of an analog computer.

Apologies if this is a standard question in a misguided disguise, this has probably been answered already. I would appreciate any pointer.

EDIT: Let me try to reformulate my question. Consider the following model of computation: Just like with a quantum computer, each qubit is a superposition $a|0\rangle + b|1\rangle$. However, we now postulate that the computer has only finite precision, i.e. that the superposition coefficients $a$,$b$ must be contained in a *discrete set* of values, for example $a,b,\in \{0.1,0.2,\dots,1.0\}$. This is equivalent to a "rounding error", where each unitary operation "rounds" the coefficients to the ones from the discrete set of values. Clearly, this model of computation is entirely classical, as each qubit can only take a finite number of superpositions, which we can encode by a classical bit string.

> How do quantum computers go beyond the "finite precision coefficients" while avoiding the "analog computers with infinite precision are too powerful" problem?

**Tags:** quantum-computing
> **Comments:**
> **username_1**: Your question is indeed a standard objection ([#6 in this 2006 lecture by Scott Aaronson](http://www.scottaaronson.com/democritus/lec14.html)) against quantum computers.  
> **username_2**: You can ask this question at: https://quantumcomputing.stackexchange.com/ .  

---

## 2 answers

### Answer by username_0 on 2017-05-14. Score: 7 | Accepted answer

It appears that my question about "numerical accuracy" / error correction for qubits is nicely answered in the bible of quantum computation, [M.A. Nielsen and I.L. Chuang, "Quantum Computation and Quantum Information", Oxford Univ. Press, 2010](http://www.cambridge.org/de/academic/subjects/physics/quantum-physics-quantum-information-and-quantum-computation/quantum-computation-and-quantum-information-10th-anniversary-edition?format=PB&isbn=9781107002173), chapter 10, in particular section 10.3.1. This book is great, I think that it is both very readable and very thorough!

The key point is the following: Yes, errors may be introduced during the calculation so that the superpositions becomes more and more "inaccurate" in small ways. Then, it may seem very strange that in many papers on error correction in quantum computation, authors often only correct for a few types of errors, in particular *bit flip* errors ($|0\rangle\leftrightarrow|1\rangle$) and *sign flip* errors ($|1\rangle\to -|1\rangle$). What about small deviations in superposition coefficients? The answer is: If you correct for the former kind of error, then the latter ones are accounted for as well! (Theorem 10.2 in the book.) The reason is that if you account for bit and sign flip errors, then you automatically account for any *linear combination* of these errors, which now includes small deviations in the coefficients as well. Hurray!

In general, when thinking about qubits, it is not a good idea focus on the fact that the superposition coefficients can be arbitrary real numbers. Sure, Shor's algorithm requires a fairly precise cancellation of these coefficients. But a better point of view is to think of a qubit as something much closer to a classical bit, which has only two discretes states $0$ and $1$, than to a high precision real number from the interval $[0,1]$. The point is that when we try to *physically* measure a qubit, we only ever get one of two discrete answers (albeit with interesting probabilities), so it's pretty much discrete.

If we compare analog and quantum computers, then it is fair to say that an analog computer tries to encode as much information as possible in high precisions real numbers, whereas a quantum computer has essentially just discrete bits with a little bit of "quantum extra". Then the key point to the computational power of quantum computers is not that a qubit contains real numbers, but that qubits combine by taking the tensor product of Hilbert spaces ($H\_1 \otimes H\_2$) whereas analog computers combine by just adding more real numbers, corresponding to the direct sum of vector spaces ($V\_1 \oplus V\_2$). The "little quantum extras" combine into something useful if we add many of them.

Also note that at the time of this writing, it is totally unclear whether quantum computers are really more powerful than classical computers. As far as I am aware of, there is no "genuine" (no oracles) problem that can be solved efficiently *only* with a quantum computer, i.e. where we have proof that a classical computer can't do it efficiently. Quantum computers certainly don't solve the $NP = P$ problem.

> **Comments:**
> **username_1**: You do not count factoring of large numbers (or any abelian hidden subgroup problem) to be a genuine problem ?  
> **username_1**: Nice answer to your own question  
> **username_0**: @FrédéricGrosshans I do count factoring of large numbers among the genuine problems, it's just that we have no proof that it can be efficiently solved *only* with a quantum computer. I have edited my answer to reflect that.  
> **username_1**: Recently, there has been a lot of research a set of non-oracle problems, like boson sampling, which are known to be efficiently solvable on quantum computers, but are hard to solve on classical computers, unless the [polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy) collapses to the 3rd level. I don’t know if these problems count as genuine (they are not oracle based, but are totally artificial), or if the separation can be considered proved, since they rely on a conjecture on the PH, but I think it is the best we have know  

---

### Answer by username_3 on 2017-05-12. Score: 3

An interesting analysis of error propagation has been published last february on QIP.
Arxiv version: <https://arxiv.org/abs/1610.05223>

Quantum Error Correction (QEC) for state preservation is a major topic in QC. You may find plenty of theoretical and experimental papers on QEC. For example: <http://www.nature.com/nature/journal/v519/n7541/full/nature14270.html>

> **Comments:**
> **username_0**: This looks interesting, but I'm not quite sure how to connect it to my question. I have edited my question to hopefully better reflect what I mean to ask.  

---

