3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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, 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.

$\endgroup$
  • $\begingroup$ You do not count factoring of large numbers (or any abelian hidden subgroup problem) to be a genuine problem ? $\endgroup$ – Frédéric Grosshans May 16 '17 at 13:15
  • 1
    $\begingroup$ Nice answer to your own question $\endgroup$ – Frédéric Grosshans May 16 '17 at 14:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Heinrich Apfelmus May 17 '17 at 8:53
  • $\begingroup$ 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 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 $\endgroup$ – Frédéric Grosshans Jul 31 '17 at 16:12
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Heinrich Apfelmus May 12 '17 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.