This post is kindly contributed by Sean Barrett, commenting on my recent paper “Error tolerance and tradeoffs in loss- and failure-tolerant quantum computing schemes”. Warning: this is a technical post.

Hi Peter,

I think you make some interesting points in this paper, which are well worth bearing in mind for anyone developing error tolerant schemes for quantum computation.

I just have a few comments.

You use the somewhat pejorative term “exponential blow out” to describe how the dephasing noise is amplified in schemes where the gates are non deterministic, but fail in a heralded way – in particular you argue that this is as a result of the extra measurements that must be performed to remove redundant qubits from the cluster. You say that the effective error teleported to the remaining qubit is

peff = 1 – (1-perr)^n

where peff is the effective error rate on the remaining unmeasured qubit, perr is the physical depolarising error per qubit, and n is the number of redundant qubits that must be removed.

There’s a couple of things to say about this equation. Firstly, it’s not immediately clear to me that this applies to all graph states, or just to GHZ-like graphs in which one qubit is connected to all the others. It would be nice to see a more explict argument for how errors are “teleported” in linear (1-d) cluster states, for example. One other point in this regard is that the paper Phys. Rev. A 73, 012304 (2006), we give a procedure for building 2-d cluster states, which is quite different from the one you analyse (I think the difference ultimately stems from the fact that Duan and Raussendorf have different physical assumptions about what happens when their gates fail). I would be interested to know how the errors accumulate using this method (which is also quite similar to the one given by Browne and Rudolph in Phys. Rev. Lett. 95, 010501 (2005)).

Secondly, your claim of an “exponential blow out” is based on the fact that the “overhead cost” n appears in the exponent of this expression. Later, you point out that n is proptional to 1/pgate, where pgate is the success probability of performing a single 2-qubit gate. What I want to point out is that your expression for peff is exactly what one would expect for the total probability of obtaining at least one error after n Bernoulli trials of a process where the error probability is *fixed* for each trial. This is a very common situation, for example, if I buy a lottery ticket each week for n weeks, the total probability of me winning the jackpot at least once will be given by your expression if I interpret perr as the probability of my winning it on any given week. In this situation, is it reasonable to say that there is an “exponential blowout” in the probability of my winning the lottery jackpot at least once? Only if I keep buying tickets for millions of weeks. For any shorter timescale, most people would reasonably describe my total chances as increasing
*linearly* with n.

A little bit of manipulation on your expression shows that (assuming
perr< <1) we can write it as

peff = 1-exp( -perr*n)

Now if we take n = A/pgate, (which you argue is the scaling for the particular cluster-growing scheme you discuss), where A is some constant factor, it’s clear that the error really grows linearly with 1/pgate, and the exponential behaviour only kicks in when A/pgate ~= perr. If A is a constant of order 1, what this says is that we only have a significant problem if the success probability for the gate is the same order of magnitude as the depolarizing error probability.

For larger values of pgate, what we have is linear scaling in 1/pgate. This is not so surprising, although it is still perhaps something that should be an important consideration in a particular implementation using non-deterministic gates. But it’s not really a problem that’s specific to these sorts of schemes. Indeed, in most implementations that have been proposed, that I am aware of, there is some kind of time or space overhead relative the the idealised circuit model quantum computer. For instance, many implementations are retricted to nearest-neighbour qubit interactions. In this case, to perform a gate between an arbitrary pair of qubits in the computer, they must be brought close together, either using SWAP operations on fixed qubits, or, as in the case of ion trap experiments, physically moving the qubit-carrying entities around. Clearly, there’s a time overhead in doing either of these, that’s proportional to the physical size of the computer. While we’re waiting for the qubits to be moved around, they will be accumulating depolarizing errors due to the interaction with the environment. One could also argue that this overhead ultimately leads to an “exponential blow out” in the depoloarizing noise, although I would prefer not to be so pessimistic!

I also wanted to make a couple of points about the distributed QC schemes I’ve been involved with, e.g. ref [5] of your paper, and Phys. Rev. A 73, 012304 (2006), which are perhaps relevant in the light of your work. In these schemes we have a distributed architecture, in which qubits comprise of trapped atoms, ions, quantum dots, or some other solid state gadget. Each qubit sits a long way from the others, so that it can be easily controlled by local control fields, and so that the decoherence processes can be well characterised and understood. We introduce entanglement between pairs of qubits using a single- (or few-) photon interference effect, which has this property that it does not always work (either because of photon loss, or in the case of our first paper, because the success probabiliy is inherently less than 1/2.) Now, of course this non-deterministic entangling scheme introduces overheads into our computing scheme, relative to one in which the gate operations are deterministic, and therefore may lead to the sort of error amplification you describe. But the hope is that there are other aspects of these schemes that more than compensate for this problem.

For instance, because we can engineer each qubit in isolation from the others, one can imagine that this makes the process of characterising decoherence and eliminating error processes easier (e.g. process tomography on a single isolated qubit is much easier than on a register containing thousands of qubits which may have residual interactions with oneanother). So we might be able to make perr very small indeed.

Furthermore, since we are not limited to nearest neighbour interactions, we don’t have a particular problem with the overhead involved in entangling distant qubits (although of course we do, in a sense, transmit entanglement via photons, so ultimately the finite speed of light will become a problem…).

Finally, because we are computing with graph/cluster states, there are some tricks we can do to reduce the “hidden overheads” inherent in many algorithms and protocols – e.g. we can potentially elimninate all the Clifford group parts of the algorithm by directly preparing appropriate graph states.

Cheers,
Sean

See the comments section below for follow up discussion on this

Yesterday I completed a new paper with Tim Ralph and Bill Munro, entitled “Error tolerance and tradeoffs in loss- and failure-tolerant quantum computing schemes”.

One of the biggest problems facing the development of useful quantum computers is the introduction of noise. Broadly speaking, there are two types of noise which are particularly common: loss, and so-called depolarizing noise. Loss noise simply corresponds to individual qubits being lost. Depolarizing noise is where the actual state (i.e. the logical value) of qubits becomes corrupted. One of the big research areas in quantum computing is quantum error correction. This is the study of techniques for tolerating noise in quantum circuits. Recently there have been several extremely promising techniques proposed for dealing with the former type of noise – loss. In this paper we have shown that these techniques generally achieve loss tolerance at the expense of tolerance against depolarizing noise. Since a useful quantum computer will require tolerance against both these types of noise, this limits the use of these loss-tolerant approaches enormously.

The consequence of all this is that unfortunately the requirements for building a quantum computer (in terms of qubit loss) are somewhat more stringent than many of us have been believing.

I’ve just submitted my latest paper with Tim Ralph to Physical Review A, entitled Error models for mode-mismatch in linear optics quantum computing. Previously I’ve done a lot of work into the effects of mode-mismatch in linear optics quantum computing (LOQC) (see previous physics posts for explanations of both these terms). This paper focusses on a basic building block of LOQC, called the parity gate, which is fundamental to many recent LOQC proposals, most notably the cluster- and parity-state approaches. Both these approaches are very promising and have completely changed the nature of the LOQC playing field. It is important to understand how errors are introduced in these models, of which mode-mismatch is one of the most dominant.

In this paper (joint work will Tim Ralph and Bill Munro) we examine a recent proposal for entanglement purification which may play an important role in upcoming quantum information processing applications. Like most proposals of this nature, the original analysis was performed in a highly idealized manner. Here we follow up on this proposal and examine various effects which will inevitably be introduced in real-world implementations. From this we can get an idea of how tolerant the scheme is to such effects (which turns out to be very). Understanding this is important for two reasons. Firstly, experimentalists will understand how well they can expect the scheme to work given the technology they have available to them. Secondly, it provides insight into what sort of technological developments need to be prioritised.

Photo-detectors are devices which detect individual photons, or particles of light. They play a central role in any sort of quantum optics experiment, where ultimately we rely on photo-detection to perform measurements. They also play a fundamental role in linear optics quantum computing, my area of research.

Theoreticians typically treat photo-detectors in a highly idealized manner, which excludes many important effects. In this paper we present more advanced models for photo-detectors which include such effects, allowing for more realistic modeling of photo-detection in quantum optics. Specifically, the effects we discuss are:

• Detector efficiency: When a photon hits a photo-detector the detector doesn’t necessarily trigger. Instead, the detector might miss the photon and think that there are fewer photons than there actually are.
• Dark-counts: The opposite effect, where a photo-detector accidentally triggers even if there is no photon.
• Dead-time: When a photo-detector triggers, it typically becomes inactive for a short period of time. During this dead-time the detector effectively has zero efficiency.
• Bandwidth: Light comes in many different frequencies. Any detector will only respond to a certain range of frequencies, referred to as the spectral bandwidth.
• Resolution: When a photo-detector detects a photon, we would ideally like to have as much information about the photon as possible. For example, we would like to know exactly what the frequency of the photon was. In practice, detectors have finite resolution, which limits how much information about a photon’s frequency the detector can extract.
• Imperfect information: Aside from the restrictions due to resolution, a detector may not faithfully convey all the information it has about the detected photon to the user. For example, even if the detector obtains very precise information about the frequency of a photon, it may not be accessible to us.

All of these phenomena have very significant effects in quantum optics experiments and can completely change the behaviour of quantum optical systems, which is why having accurate models is important.

Today I am proud to announce the availability of version 0.1 of Quack!, a MATLAB package for simulating simple quantum circuits. While there a plenty of programs out there for doing exactly the same thing, I decided to write my own for a bit of fun. The entire package operates from within the MATLAB environment, which has the advantage that MATLAB’s in-built flow-control and plotting commands are available.

Features include:

• Single qubit and Bell state preparation
• Single qubit unitary gates, with built in Pauli, rotation, Hadamard, phase and pi/8 gates
• Controlled-NOT, controlled-sign, swap gates and Toffoli gates
• Arbitrary depolarizing, bit-flip and phase-flip channels
• Single qubit and Bell measurements
• Classically controlled operations
• The ability to view the reduced density matrices of single qubits in a system

Quack! comes with several example programs which demonstrate useage and functionality.

You can download Quack! here

In a recent post to his blog, David Deutsch, one of the founders of the field of quantum computing, claims that he now believes quantum computers are only years away. He says that while he previously believed quantum computing to be decades away, recent theoretical developments have changed his view. In particular, he cites the discovery of cluster state quantum computing as being a major theoretical breakthrough.

Cluster state quantum computing is a different way of thinking about quantum computing. In the standard model for quantum computing, we construct algorithms using circuits, much like in classical electronics or computer science. The cluster state model, on the other hand, is completely different. Instead of constructing a circuit, we prepare a large entangled state. Once this state is prepared, we simply perform a sequence of measurements on the state. The choice of measurements we perform implements the algorithm. This may seem rather uninteresting, but this model for quantum computation has numerous benefits over the standard circuit model. In particular, in many schemes, including linear optics quantum computing (my field of research), using the cluster state model massively reduces the physical requirements for building a quantum computer.

While I agree completely with Deutsch that cluster state quantum computing has been extremely positive, and represent a major theoretical development, I completely disagree with his view that, as a result, quantum computers are just around the corner. The reason for this is that while the cluster state model reduces the physical requirements to implement a quantum computer, it does not obviate the exquisite level of control which is required over microscopic systems. Quantum systems are extremely sensitive to noise, and the margins for error are extremely low. Unfortunately, in all of the major candidate systems for implementing quantum computing, achieving this level of control is still a major obstacle, and will likely remain so for quite a while to come.

Having said all this, I sincerely hope that I am wrong and Deutsch is right.