16

Magic states are certain states that have very nice properties with respect to fault-tolerant quantum computation. In the vast landscape of quantum gates, there is a crude but useful distinction to be made between Clifford gates and all other gates (also referred to as the inspired non-Clifford gates). The set of Clifford gates is in technical terms the ...


14

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


11

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

Throughout this answer, the norm of a matrix $A$, $\left\lVert A\right\rVert$ will be taken to be the spectral norm of $A$ (that is, the largest singular value of $A$). The solovay-Kitaev theorem states that approximating a gate to within an error $\epsilon$ requires $$\mathcal O\left(\log^c\frac 1\epsilon\right)$$ gates, for $c<4$ in any fixed number of ...


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


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


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


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


6

Classical Version Think about a simple strategy of classical error correction. You've got a single bit that you want to encode, $$ 0\mapsto 00000\qquad 1\mapsto 11111 $$ I've chosen to encode it into 5 bits, but any odd number would do (the more the better). Now, let's assume some bit-flip errors have occurred, so what we have is $$ 01010. $$ Was this ...


6

The Toric code is an error correcting code. The distance of the code (I.e. the number of local operations required to convert one logical state into an orthogonal one) is equal to $N$, where the Toric code is defined on an $N\times N$ grid. One of the places that the performance of the Toric code really wins out is that although it is only distance $N$, the ...


6

It is any state that, if you have an unlimited supply of them, can be used to give you universal quantum computation when used in conjunction with perfect Clifford operations. The standard example is that if you can produce the state $(|0\rangle+e^{i\pi/4}|1\rangle)/\sqrt{2}$, then you can combine this with Clifford operations in order to apply a $T$ gate (...


6

In fault-tolerant quantum computing, we make a distinction between physical qubits and logical qubits. The logical qubits are the ones we use in our algorithm. So if our input is a number stored in binary across $n$ qubits (as in Shor's algorithm), then these $n$ qubits are logical qubits. When we ask for a quantum Fourier transform on a collection of ...


5

Quantum error correction concerns errors that happen on qubits; it does not provide any protection against errors in operations on those qubits. Note however, that an error on an operation can be seen as the perfect operation plus some error 'on the qubit'. It is, however, the case that, without any precaution, the added operations introduced by error ...


5

First of all, the two conditions for fault tolerant measurements are: A single error gives no more than one error per block of qubits The measurement result needs to be correct with probability $1-\mathcal O\left(p^2\right)$ The preparation step creates the state $\frac{1}{\sqrt{2}}\left(\left|000\right>+\left|111\right>\right)$ (the three qubit 'cat ...


5

First a matter of terminology. I don't have my copy of Nielsen & Chuang to hand, but I would have thought that the bottom, extra qubit, is the one that is the ancilla. I am also not entirely convinced that the errors you're talking about can be correct. You seem to be talking about $Z$ errors, but giving results that correspond to $X$ errors. (If a $Z$-...


5

In addition to the accepted answer and @user1271772's examples, here is a circuit primitive referred to explicitly as a "T-gate gadget" in [1] (originally appearing in [2]): where application of the $S$ gate is conditioned on measuring a "1" on the ancilla. The way this works is, for $|A\rangle = \frac{1}{\sqrt{2}} (|0\rangle + e^{i\pi/...


4

I believe that the Centre for Engineered Quantum Systems, School of Physics, The University of Sydney and the Center for Theoretical Physics, Massachusetts Institute of Technology use of a tensor network decoder of Bravyi, Suchara and Vargo (BSV), to achieve the highest error correction threshold to date. In their whitepaper from last December, "Ultrahigh ...


4

There is a good mathematical answer already, so I'll try and provide an easy-to-understand one. Quantum error correction (QEC) is a (group of) rather complex algorithm(s), that requires a lot of actions (gates) on and between qubits. In QEC, you pretty much connect two qubits to a third helper-qubit (ancilla) and transfer the information if the other two ...


4

We want to compare an output state with some ideal state, so normally, fidelity, $F\left(\left|\psi\right>, \rho\right)$ is used as this is a good way to tell how well the possible measurement outcomes of $\rho$ compare with the possible measurement outcomes of $\left|\psi\right>$, where $\left|\psi\right>$ is the ideal output state and $\rho$ is ...


4

1) Magic state distillation is performed within the surface code If you mean the distillation circuit is implemented with encoded logical qubits instead of raw physical qubits, then yes. 2) The initial step of producing many copies of raw noisy T-states is done through the direct use of a non-fault tolerant T-gate Yes, the initial T states fed into the ...


4

This is a very interesting question. Indeed, CP maps - and this includes the operations used in the error correction (measurement and subsequent unitaries) - will always decrease the trace norm. The answer is that if you take a (strictly) contractive map on, say, a qubit, and consider how it acts if you apply it to many qubits, there will always be some ...


4

Consider a quantum computer that can: Prepare qubits in state $|0\rangle$ Apply unitary gates from the Clifford group Measure qubits in the $X$, $Y$, and $Z$ bases This seems ideal because: We know how to implement all three functionalities quite easily (compared to more complicated gates or measurements) We can design algorithms for such a quantum ...


4

If it were me, I'd write out the $k$ $N$-qubit stabilizer generators in a $k\times 2N$ binary matrix, where each row corresponds to a stabilizer generator, with the first $N$ bits being the positions of the $X$ rotations, and the second $N$ being the positions of the $Z$s. A CSS code can be converted into a block structure where there are rows with only $X$ ...


4

"As far as I understand there aren't many rigorous results on performance of these algorithms, similar to many classic machine learning approaches." You are correct in that, unlike Grover's algorithm where we can prove that a search that would cost $\mathcal{O}(N)$ on a classical computer can be done with only $\mathcal{O}(\sqrt{N})$ on a quantum ...


3

Content wise very similar course but different name Quantum Information Science I (three parts - part 1, 2, and 3) and Quantum Information Science II were $49 per course as verified certified learning outcome - a series of 3 courses + 1 more extra course on edX. Now the course has been taken down; at least no more new enrollments, and MITx Pro is offering ...


3

In their case, their finite set of unitary operators is closed under composition. They even have footnote that emphasizes this. You can't approximate infinite set by some finite subset with the error that is less than half the minimum distance between elements in this finite subset. This is like trying to approximate every real number from $[0,1]$ by some ...


3

Let $\mathcal{H}$ be the Hilbert space of a set of physical qubits and let $S$ be the stabilizer group of a stabilizer code $\mathcal{G} \subset \mathcal{H}$. A transversal operator $U$ on $\mathcal{H}$ implements a logical operator on $\mathcal{G}$ if it maps $\mathcal{G}$ back to itself. This can be established by showing that $U$ does not change the ...


2

You need a surprisingly large number of quantum gates to implement a quantum error correcting code in a fault-tolerant manner. One part of the reason is that there are many errors to detect since a code that can correct all single qubit errors already requires 5 qubits and each error can be of three kinds (corresponding to unintentional X, Y, Z gates). Hence ...


2

To me there seem to be two parts of this question (one more related to the title, one more related to the question itself): 1) To which amount of noise are error correction codes effective? 2) With which amount of imperfection in gates can we implement fault-tolerant quantum computations? Let me firs stress the difference: quantum error correction codes ...


2

The answer arguably depends on the problem you wish to solve with your computation. More specifically, are you wanting to optimize near-term applications in the NISQ era, or are you wanting to build a fully scalable, fault-tolerant and universe quantum computer? For the latter, you need to think about error correction. Pretty much everything that will ...


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