Gil Kalai’s blog

## Detrimental Noise

Posted on November 9, 2008 by

### John Lennon

Disclaimer: It is a reasonable belief  (look here, and here), and an extremely reasonable working assumption (look  here) that computationally superior quantum computers can be built.

(This post and the draft will be freely updated) I am struggling to meet the deadline of a week ago for a chapter regarding adversarial noise models for quantum error correction. (Update Nov 20: here is the draft; comments are welcomed. Update April 23: Here is the arxived paper, comments are welcome! ) My hypothetical model is called “detrimental.” (This is a reason substantial math postings are a bit slow recently; but I hope a few will come soon.) This project is quite central to my research in the last three years, and it often feels like running, over my head, after my own tail that might not be there. So this effort may well be a CDM (“career damaging move”) but I like it nevertheless. It is related to various exciting conceptual and foundational issues.

I do have occasionally a sense of progress, (often followed by a backtrack) and for this chapter, rather than describing detrimental noise by various (counterintuitive) properties as I always did, I think I have an honest definition of detrimental noise. Let me tell you about it. (Here is a recent useful guide: a zoo of quantum algorithms, produced by Stephen Jordan.)

## Detrimental noise

Consider a quantum memory with $n$ qubits at a state $\rho_0$. Suppose that $\rho_0$ is a tensor product state. The noise affecting the memory in a short time interval can be described by a quantum operation $E_0$. Lets suppose that $E_0$ acts independently on different qubits and, for qubit $i$ with some small probability $p_i$, $E_0$ changes it state to the maximum entropy state $\tau_i$.

This is a very simple form of noise that can be regarded as basic to understanding the standard models of noise as well as of detrimental noise.

In the standard model of noise, $E_0$ describes the noise of the quantum memory regardless of the state $\rho$ stored in the memory. This is a quite natural and indeed expected form of noise.

A detrimental noise will correspond to a scenario in which, when the quantum memory is at a state $\rho$ and $\rho= U \rho_0$, the noise $E$ will be $U E_0 U^{-1}$. Such noise is the effect of first applying $E_0$ to $\rho_0$ and then applying $U$ to the outcome noiselessly.

Of course, in reality we cannot perform $U$ instantly and noiselessly and the most we can hope for is that $\rho$ will be the result of a process. The conjecture is that a noisy process leading to $\rho$ will be subject to noise of the form we have just described. A weaker weaker conjecture is that detrimental noise is present in every natural noisy quantum process. I also conjecture that damaging effects of the detrimental noise cannot be canceled or healed by other components of the overall noise.When we model a noisy quantum system either by a the qubits/gates description or in other ways we make a distinction between “fresh” errors which are introduced in a single computer cycle (or infinitesimally when the evolution is described by a continuous model) and the cumulative errors along the process. The basic insight of fault tolerant quantum computing is that if the incremental errors are standard and sufficiently small then we can make sure that the cumulated errors are as well. The conjecture applies to fresh errors.

(Updated: Nov 19; sorry guys, the blue part is over-simplified and incorrect; But an emergency quantifier replacement seemed to have helped; it seems ok now)  The definition of detrimental noise for general quantum systems that we propose is as follows:

A detrimental noise of a quantum system at a state $\rho$ commutes with every some non-identity quantum operation which stabilizes $\rho$.

Note that this description,

Just like for the standard model of noise, we do not specify a single noise operation but rather gives an envelope for a family of noise operations.

In the standard model of noise the envelope $\cal D_{\rho}$ of noise operations when the computer is at state $\rho$ does not depend on $\rho$. For detrimental noise there is a systematic relation between the envelope of noise operations ${\cal D}_\rho$ and the state $\rho$ of the computer. Namely,

${\cal D}_{U\rho} = U {\cal D}_\rho U^{-1}$.

## Why is it detrimental?

Detrimental noise leads to highly correlated errors when the state of the quantum memory is highly entangled. This is quite bad for quantum error-correction, but an even more devastating property of detrimental noise is that the notion of “expected number of qubit errors” becomes sharply different from the rate of noise as measured by fidelity or trace distance. Since conjugation by a unitary operator preserves fidelity-metric, the expected number of qubit errors increases linearly with the number of qubits for highly entangled states.

Here is another little thing from my paper that I’d like to try on you:

## A riddle: Can noise remember the future?

Suppose we plan a process and carry it out up to a small amount of errors. Can there be a systematic relation between the errors at some time and the planned process at a later time?

Context: In the context of quantum error-correction and fault-tolerant quantum computing, the noise depending on the past process is regarded as a possibility: the environment can “remember” traces of the process leading to the present state. But I did not encounter the possibility that the noise at a certain time can systematically depend on the planned process at a later time. Can it?

My answer: yes it can! The assumption that the entire process was carried up to few errors implies a statistical relation between the entire evolution of the performed process, and, in particular, the incremental errors at a given time, and the entire planned process.

Example: A gymnast performs a complicated routine. Her errors are observed and are taken into account and her overall score is 9.7525. Is it true that the nature of the errors at a specified moment of the routine may depend on the entire planned routine?

### Like this:

This entry was posted in Computer Science and Optimization, Controversies and debates, Physics and tagged Fault-tolerance, Noise, Quantum computers, Quantum error-correction. Bookmark the permalink.

### One Response to Detrimental Noise

1. Gil Kalai says:

I added a link to an arxived version of the paper.

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 29, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9229846000671387, "perplexity_flag": "middle"}