What exactly is meant by "noise" in the following context?

Question

The strengthened version of the Church-Turing thesis states that:

Any algorithmic process can be simulated efficiently using a Turing machine.

Now, on page 5 (chapter 1), the book Quantum Computation and Quantum Information: 10th Anniversary Edition By Michael A. Nielsen, Isaac L. Chuang goes on to say that:

One class of challenge to the the strong Church Turing thesis comes from the field of analog computation. In the years since Turing, many different teams of researchers have noticed that certain types of analog computers can efficiently solve problems believed to have no efficient solution on a Turing machine. At the first glance these analog computers appear to violate the strong form of the Church-Turing thesis. Unfortunately for analog computation it turns out that when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances; they cannot efficiently solve problems which are not solvable on a Turing machine. This lesson – that the effects of realistic noise must be taken into account in evaluating the efficiency of a computational model – was one of the great early challenges of quantum computation and quantum information, a challenge successfully met by the development of a theory of quantum error-correcting codes and fault-tolerant quantum computation. Thus, unlike analog computation, quantum computation can in principle tolerate a finite amount of noise and still retain its computational advantages.

What exactly is meant by noise in this context? Do they mean thermal noise? It's strange that the authors did not define or clarify what they mean by noise in the previous pages of the textbook.

I was wondering if they were referring to noise in a more generalized setting. Like, even if we get rid of the conventional noise - like industrial noise, vibrational noise, thermal noise (or reduce them to negligible levels), noise could still refer to the uncertainties in amplitude, phase, etc, which arise due to the underlying quantum mechanical nature of the system.

Answer 1

As an addition to Nat's answer, it's worth mentioning that 'noise' is a specific concept¹ in quantum computing. This answer will use Preskill's lecture notes as a basis.

In essence, noise is indeed considered to be something that could be described as 'thermal noise', although it should be noted that it is an interaction with a thermal environment causing noise, as opposed to noise in and of itself. Approximations are made that means this noise can be described using quantum channels, which is what Nielsen & Chuang seem to be referring to, as they discuss this in chapter 8.3 of that very textbook. The most common types of noise described in this manner are: depolarising, dephasing and amplitude damping, which will be very briefly explained below.

In a bit more detail²

Start with a system with Hilbert space $\mathcal{H}_S$, coupled to a (thermal) bath with Hilbert space $\mathcal{H}_B$.

Take the density matrix of the system and 'course grain' it into chunks of $\rho\left(t + n\,\delta t\right)$. Make the assumption that the interaction is Markovian, that is, the environment 'forgets' much quicker than the coarse graining time and that whatever you're trying to observe occurs over a time much longer than the coarse graining time.

Express the density matrix at $t+\delta t$ as a channel acting on the density matrix at time $t$: $\rho\left(t + \delta t\right) = \varepsilon_{\delta t}\left(\rho\left(t\right)\right)$.

Expand this to first order in $\delta t$ to get $\varepsilon_{\delta t} = \mathrm{I} + \delta t\,\mathcal{L}$. As a channel, it must be completely positive and trace preserving, so $\varepsilon_{\delta t}\left(\rho\left(t\right)\right) = \sum_aM_a\rho\left(t\right)M_a^\dagger$ and satisfies $\sum_aM_a^\dagger M_a = \mathrm{I}$.

This gives a non-unitary quantum channel described by the Lindblad Master equation $$\dot\rho = -i\left[H, \rho\right] + \sum_{a>0} \gamma_a\left(L_a\rho L_a^\dagger - \frac{1}{2}\lbrace L^\dagger_aL_a, \rho\rbrace\right),$$ where $\gamma_a$'s are always positive for Markovian evolution.

This can also be written as $H_{\mathrm{eff}} = H - \frac{i}{2}\sum_a\gamma_aL_a^{\dagger}L_a$, with an additional term, such that the evolution can be written as $$\dot\rho = -i\left[H_{\text{eff}}, \rho\right] + \sum_{a>0} \gamma_aL_a\rho L_a^\dagger.$$

This now looks equivalent to the Kraus operator representation of a channel, with Kraus operators $K_a \propto L_a$ (as well as an additional Kraus operator to satisfy $\left[H_{\text{eff}}, \rho\right]$). Any non-trivial Lindbladian can then be described as noise, although in reality, it is an approximation of evolution of an open system.

Some common types of noise³

Trying out various different forms of $L_a$ gives different behaviours of the system, which give different possible noises, of which there are a few common ones (in the single qubit case, anyway):

1. Dephasing: Causes the system to decohere - this gets rid/reduces the entanglement (i.e. coherence) of the system, necessarily making it more mixed, unless already maximally mixed $$\varepsilon\left(\rho\right) = \left(1-\frac{p}{2}\right)\rho + \frac{1}{2}\sigma_z\rho\sigma_z$$

2. Depolarising: Upon measuring, either a bit flip ($\sigma_x$), phase flip ($\sigma_z$), or both bit and phase ($\sigma_y$) will have occurred with some probability $$\varepsilon\left(\rho\right) = \left(1-p\right)\rho + \frac{p}{3}\left(\sigma_x\rho\sigma_x + \sigma_y\rho\sigma_y + \sigma_z\rho\sigma_z\right)$$

3. Amplitude Damping: Represents the system decaying from $\lvert 1\rangle$ to $\lvert 0\rangle$, such as when an atom emits a photon. Leads to a simple version of the coherence times $T_1$ (decay of $\lvert 1\rangle$ to $\lvert 0\rangle$) and $T_2$ (decay of the off-diagonal terms). Described by the Kraus operators $$M_0 = \begin{pmatrix}1 & 0 \\ 0 & \sqrt{1-p}\end{pmatrix} \text{ and } M_1 = \begin{pmatrix}0 & \sqrt{p} \\ 0 & 0\end{pmatrix},$$ giving $$\varepsilon\left(\rho\right) = M_0\rho M_0^\dagger + M_1\rho M_1^\dagger$$

---

^{1 Or rather, several very broad concepts resulting from the same fundamental idea}

^{2 I wouldn't go around calling this rigorous or anything}

^{3 Within this context, naturally}

Answer 2

Unfortunately for analog computation it turns out that when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances; they cannot efficiently solve problems which are not solvable on a Turing machine.

"Noise" appears to be used in the general sense of non-idealities in a signal:

In signal processing, noise is a general term for unwanted (and, in general, unknown) modifications that a signal may suffer during capture, storage, transmission, processing, or conversion.^[1]

Sometimes the word is also used to mean signals that are random (unpredictable) and carry no useful information; even if they are not interfering with other signals or may have been introduced intentionally, as in comfort noise.

-"Noise (signal processing)", Wikipedia

For an example of what they're talking about, let's consider a simple circuit:

$$ \require{enclose} \def\place#1#2#3{\smash{\rlap{\hskip{#1pt}\raise{#2pt}{#3}}}} % \bbox[10pt]{\enclose{box}{\phantom{\Rule{250pt}{75pt}{0pt}}}} % \place{-275}{70}{\enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{resistor} \\ \text{set resistance:}~R \end{array} }}} % \place{-270}{0}{ \enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{power source} \\ \text{set voltage:}~V \end{array} }}} % \place{-55}{30}{ \enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{current meter} \\ \text{measured current:}~I \end{array} }}} $$

Since we can select both $V$ and $R$ and we know Ohm's law, $I=\frac{V}{R}$, we can use this circuit to divide numbers for us:

1. Select some division problem to perform, $\frac{a}{b}=?$.

2. Set the voltage source to $V=a~\mathrm{V}$.

3. Set the resistor to $R=b~\mathrm{\Omega}$.

4. Measure $I=?~\mathrm{A}$ to get the result!

This is a simple analog computer that can divide numbers without need for us to perform the math in some other manner, e.g. digital logic.

But what's really cool about this? If we're naive, we might believe that it can do real computation:

In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of real numbers. Within this theory, it is possible to prove interesting statements such as "The complement of the Mandelbrot set is only partially decidable."

These hypothetical computing machines can be viewed as idealised analog computers which operate on real numbers, whereas digital computers are limited to computable numbers.

-"Real computation", Wikipedia

The thing's that Ohm's law uses real-number values, $\left\{V,I,R\right\}{\in}\mathbb{R}$. If we believe that these values actually have infinite precision, then we can perform multiplication or division with infinite precision in finite time; this is a feat that a Turing machine can't perform with finite-time operations.

Anyway, back to the original quote:

Unfortunately for analog computation it turns out that when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances; they cannot efficiently solve problems which are not solvable on a Turing machine.

They're basically saying that, whenever someone's come up with a scheme like this, the non-idealities of the situation (noise in the signals, design, etc.) tend to derail the idealistic expectations.

The quoted excerpt seems to use this as a jumping-off point to discuss how quantum computers aren't as limited by this problem as classical analog computers often seem to have been.

Answer 3

Asking the author to clarify would give you the exact answer you are looking for. However, based upon the context provided I believe this may be related to the problem quantum noise spectroscopy attempts to solve.

Noise

According to a team of Dartmouth researchers led by Professor Lorenza Viola,

These quantum properties are essential for quantum computing, but they are easily lost through decoherence, when quantum systems are subject to "noise" in an external environment.

The quantum properties she is referring too are quantum system properties such as the ability to be in a superposition of two different states simultaneously as stated in the same article.

My Conclusion

Therefore, based upon both the context provided in the question and the context provided by the team of Dartmouth researchers, I would conclude that the noise the book refers to is environmental noise.