18

That doesn't scale well. After a moderately long calculation you're basically left with the maximally mixed state or whatever fixed point your noise has. To scale to arbitrary long calculations you need to correct errors before they become too big. Here's some short calculation for the intuition given above. Consider the simple white noise model (...


15

The majority of useful/relatively efficient algorithms1 for quantum computers belong to the 'bounded-error quantum polynomial time' (BQP) complexity class. By this definition, you want the 'failure rate' of any quantum algorithm to be $\leq\frac{1}{3}$, or $\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$, although the result may still be within some ...


14

What we can easily prove is that there's no smaller non-degenerate code. In a non-degenerate code, you have to have the 2 logical states of the qubit, and you have to have a distinct state for each possible error to map each logical state into. So, let's say you had a 5 qubit code, with the two logical states $|0_L\rangle$ and $|1_L\rangle$. The set of ...


13

The terminology of 'surface code' is a little bit variable. It might refer to a whole class of things, variants of the Toric code on different lattices, or it might refer to the Planar code, the specific variant on a square lattice with open boundary conditions. The Toric Code I'll summarise some of the basic properties of the Toric code. Imagine a square ...


13

A proof that you need at least 5 qubits (or qudits) Here is a proof that any single-error correcting (i.e., distance 3) quantum error correcting code has at least 5 qubits. In fact, this generalises to qudits of any dimension $d$, and any quantum error correcting code protecting one or more qudits of dimension $d$. (As Felix Huber notes, the original ...


11

If the error rate were low enough, you could run a computation a hundred times and take the most common answer. For instance, this would work if the error rate were low enough that the expected number of errors per computation was something very small — which means that how well this strategy works would depend on how long and complicated a computation ...


11

Code spaces and code-words A quantum error correcting code is often identified with the code-space (Nielsen & Chuang certainly seem to do so). The code space $\mathcal C$ of e.g. an $n$-qubit quantum error correction code is a vector subspace $\mathcal C \subseteq \mathcal H_2^{\otimes n}$. A code word (terminology which was borrowed from the ...


10

That is indeed the most important question at the moment! Superconducting qubits currently have the biggest devices. But will they continue to scale? Will short coherence times make it too hard for error correction to keep up? Trapped ions are not far behind. But they have their own scalability issues. Spin qubits should be great for scaling once they get ...


10

The surface codes are a family of quantum error correcting codes defined on a 2D lattice of qubits. Each code within this family has stabilizers that are defined equivalently in the bulk, but differ from one another in their boundary conditions. The members of the surface code family are sometimes also described by more specific names: The toric code is a ...


9

Majoranas are anyons (a type of quasiparticles wich behave differently from fermions and bosons), and so are related to the idea of topological quantum computation. This means that a good implementation should have properties that help deal with noise built in. Their main problem is that it is difficult to prepare physical systems which behave as Majorana ...


9

Elaborating somewhat on Mithrandir24601's response — The feature you're worried about, that a quantum computer might produce a different answer on the next run of the computation, is also a feature of randomised computation. It is good in some ways to be able to obtain a single answer repeatably, but in the end it is enough to be able to obtain a ...


9

Based on your question I think that you were not looking for the correct term. Error correction codes are methods in order to detect and correct possible errors that arise in qubits due to the effect of decoherence. The term fault-tolerant quantum computing refers to the paradigm of quantum devices that work effectively even when its elementary components ...


8

A topological quantum computer could be made by using an exotic phase of matter in which anyons arise as localized effects (such as quasiparticles or defects). In this case, errors typically cost energy, and so the probability is suppressed for small temperatures (though it will never be zero). A topological quantum computer could also be made (or one could ...


8

Now, adding to M. Stern's answer: The primary reason as to why error correction is needed for quantum computers, is because qubits have a continuum of states (I'm considering qubit-based quantum computers only, at the moment, for sake of simplicity). In quantum computers, unlike classical computers each bit doesn't exist in only two possible states. For ...


8

Yes, the physical implementation is the constraint. If you look at the image of the processor you'll notice the connections between qubits. This gives you an idea of how you can perform two qubit gates between particular qubits. Here's the documentation on the Tenerife backend. In the section titled Two Qubit gates at the bottom you can read the details. ...


8

I signed up for this series because I was interested in the 2nd and 3rd courses. There are a lot of students from different backgrounds so I think that limits the depth of what the instructors can cover. The introductory course was too easy in terms of content, however useful in the form of industry perspectives and getting to know 'who is doing what' in ...


8

The Helstrom measurement is the measurement that has the minimum error probability when trying to distinguish between two states. For example, let's imagine you have two pure states $|\psi\rangle$ and $|\phi\rangle$, and you wish to know which it is that you have. If $\langle\psi|\phi\rangle=0$, then you can specify a measurement with three projectors $$ P_{...


8

I will illustrate how one can perform operations using logical operations on the qubits, and using lattice surgery for two-qubit operations. In the diagrams below, all of the 'dots' are data qubits: measurement qubits are omitted in order to help demonstrate the basic principles more clearly. The measurement qubits are there for when you perform stabiliser ...


8

As a complement to the other answer, I am going to add the general quantum Hamming bound for quantum non-degenerate error correction codes. The mathematical formulation of such bound is \begin{equation} 2^{n-k}\geq\sum_{j=0}^t\pmatrix{n\\j}3^j, \end{equation} where $n$ refers to the number of qubits that form the codewords, $k$ is the number of information ...


7

As far as I’m aware, the surface code is still regarded as the best. With an assumption of all elements failing with equal probability (and doing so in a certain way) it has a threshold of around 1%. Note that the paper you linked to doesn’t have a 3D surface code. It is the decoding problem that is 3D, due to tracking changes to the 2D lattice over time. ...


7

This bound works by counting the number of orthogonal states that must be available. If you're encoding into $n$ qubits, you can't require more than $2^n$ orthogonal states, because that's all that's available. This is the right hand side of the bound. If you wish to encode $k$ logical qubits in a distance $2t+1$ code, then each of the $2^k$ basis states of ...


7

The key point of quantum error correction is precisely to correct the errors without collapsing the qubits, right? If we measure the encoded qubits we project the qubits to $\left|0\right>$ or $\left|1\right>$ and lose all the information in the coefficients $\alpha \left|0\right> + \beta \left|1\right>$. By measuring ancilla qubits we can know ...


7

Yes, the set of tensor products of all possible $n$ Pauli operators (including $I$) forms an orthogonal basis for the vector space of $2^n \times 2^n$ complex matrices. So see this first we notice that the space has a dimension of $4^n$ and we also have $4^n$ vectors ( the vectors are operators in this case). So we only need to show that they are linearly ...


6

In the context of scalable quantum computing, the polylog scaling needed for magic state distillation should not be a problem. Indeed, it is not the only polylog scaling we need to contend with. Using the $S$ and $T$ gates to approximate a general single qubit rotation can have a similar cost when using the Solvay-Kitaev algorithm (though this is no longer ...


6

An $[\![n,k,d]\!]$ code is a quantum error correction code which encodes $ k$ qubits in an $ n$-qubit state, in such a way that any operation which maps some encoded state to another encoded state must act on at least $d$ qubits. (So, for example, any encoded state which has been subjected to an error consisting of at most $\lfloor (d-1)/2 \rfloor $ Pauli ...


6

Classical correlations between variables occur when the variables appear random, but whose values are found to systematically agree (or disagree) in some way. However, there will always be someone (or something) that 'knows' exactly what the variables are doing in any given case. Entanglement between variables is the same, except for the last part. The ...


6

When you say "why not just measure the 3 encoded qubits directly", are you thinking that you could measure $Z_1$, $Z_2$ and $Z_3$, and that, from there, you can calculate the values $Z_1Z_2$ and $Z_2Z_3$? This is sort of true: if your only goal is to obtain the observables $Z_1Z_2$ and $Z_2Z_3$, you could do this. But that is not your end goal, which is, ...


6

The five qubit IBM devices have a ‘bow tie’ architecture, which mean that it is only possible to interact certain pairs of qubits. These are shown in the answer of Andrew O. The interaction that can be performed between these pairs of qubits is a CNOT with a particular direction. However, it is possible to implement others indirectly. For example, to ...


6

The key difference is that the Bacon-Shor code is a subsystem code, while the Shor code is a stabilizer code. They have the same stabilizer operators, but the error correction procedure is different. The canonical reference for this construction is [Poulin]. Stabilizer codes rely on measuring eigenvalues of commuting operators (the stabilizers). Because ...


6

The $t$ in $t$-design is essentially a measure of how good a job the set of gates does in terms of randomising a state (the larger t, the more random, with properly random requiring the infinite limit). Often, you want to compute the average of some function over all possible pure input states, which is equivalent to fixing the input state and averaging over ...


Only top voted, non community-wiki answers of a minimum length are eligible