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


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


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

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


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

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

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


5

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


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

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


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

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


4

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


4

This course was \$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 it for \$2250 + \$2250 = \$4500. This is 20 times higher for the same course. I see there would be number of other MOOC coming soon. One ...


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


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


2

In the dim and distant past (I.e. I don’t remember the details any more), I tried to calculate an upper bound on a fault tolerant threshold. I suspect the assumptions that I made to get there wouldn’t apply to every possible scenario, but I came up with an answer of 5.3% (non-paywall version). The idea was roughly to make use of a well-known connection ...


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


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


1

Based on what I've understood from your question, I think the interpretation of the noisy channel as the quantum algorithm may be causing unnecessary confusion. QEC should be present in the fault tolerant computing paradigm as a background operation capable of guaranteeing that qubits retain coherence of their quantum states for practical amounts of time. As ...


1

Probably the easiest way to think about this is to consider an equivalent statement for the real numbers. Consider the range $[0,1]$, for instance. You're given a finite set of real numbers within that range. If you think about these values on the number line, it should be fairly obvious that there are necessarily points that are a finite distance away, so I ...


1

The three measurements you refer to are composed of two data qubits and an ancilla. They essentially ask the question "is the state of the data qubits in the subspace spanned by $|00\rangle$ and $|11\rangle$ (in which case the measurement result on the ancilla will be $0$) or is the state in the subspace $|01\rangle$ and $|10\rangle$ (in which case the ...


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