19

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


8

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

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

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

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


6

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


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

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


5

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


5

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


5

Magic state names are not consistent across papers. For example, the state used to perform T gates via gate teleportation, equal to $\frac{1}{\sqrt{2}}\left(|0\rangle + e^{i \pi/4}|1\rangle\right)$ up to single qubit Cliffords, has been called: The $|A\rangle$ state (example 1, example2). The $|T\rangle$ state (example 1, example 2) The $|H\rangle$ state (...


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

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

Disclaimer: these links do not all fit the criterion recent. First and foremost, it is important to realize that there is no 'one' magic state, and no 'one' magic state distillation. The term 'magic state' is, loosely speaking, used to refer to any state that can be used, in conjunction with fault-tolerant Clifford operations and a specific quantum code, to ...


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

So the general definition of pseudothreshold is when the logical qubit outperforms a physical qubit. If your error model is idling error, for example, you want to find the physical value of T1 and T2 for which the physical qubits lifetime is lower than the logical qubit's lifetime. The easiest way to calculate this would be to write a simulation of the ...


3

The first answer discusses what the pseudothreshold is and how to find it, but I will try to give a few details on the difference between thresholds and pseudothresholds, since your first question does ask for both definitions. In quantum error correction (QEC), a logical qubit is encoded in many physical qubits. Given some underlying physical error rate $p$...


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