Fault-tolerant quantum computing
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 48 | |
| Author | ||
| License | CC Attribution - NonCommercial - NoDerivatives 3.0 Germany: You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/35306 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
12
23
24
29
31
37
38
00:00
Quantum computerExecution unitEmailSeries (mathematics)VotingSource codeEndliche ModelltheorieNoise (electronics)Fault-tolerant systemQuantum computerSet (mathematics)Natural numberLocal ringError messageProcess (computing)FamilySelf-organizationLoginFehlererkennungOrder (biology)Limit of a functionEvent horizonCodeBitLevel (video gaming)Database normalizationInformationPoint (geometry)Thresholding (image processing)SoftwareGame controllerForm (programming)Bit rateComputerField (computer science)ExpressionQuantum mechanicsTelecommunicationCodeCommunications protocolMathematical analysisHard disk driveQuicksortCombinational logicSocial classSemiconductor memorySurfaceData structureData miningType theoryFunctional (mathematics)Ideal (ethics)Reading (process)Electronic data processingSystem callAreaTheoryLecture/ConferenceComputer animation
05:36
Maxima and minimaClassical physicsFault-tolerant systemClassical physicsComputer simulationThresholding (image processing)SimulationError messageMereologyComputerQuicksortQuantum computerLogic gateSoftware developerComputer hardwareWell-formed formulaTheoremOrder (biology)Limit of a functionEndliche ModelltheorieNoise (electronics)Functional (mathematics)Social classDigital electronicsParameter (computer programming)Bit rateoutputFunction (mathematics)Numbering schemeMoment (mathematics)Sinc functionCalculationConnectivity (graph theory)Expert systemLine (geometry)Physical systemMultiplication signVapor barrierOperator (mathematics)Game controllerScaling (geometry)Basis <Mathematik>Power (physics)Process (computing)InformationMechanism designArithmetic meanSmartphoneBitDefault (computer science)Key (cryptography)FehlererkennungTheoryCrash (computing)ExistenceExtension (kinesiology)Point (geometry)Overhead (computing)Instance (computer science)AreaCASE <Informatik>Bound stateObservational studyField (computer science)Form (programming)1 (number)Computer animation
11:14
Quantum computerExecution unitMaxima and minimaParallel portCrash (computing)Order (biology)Physical systemLogic gateMultiplication signError messageCommunications protocolState of matterNumberFunctional (mathematics)Digital electronicsDegree (graph theory)Noise (electronics)Endliche ModelltheorieQubitMaxima and minimaFault-tolerant systemFamilyMessage passingClassical physicsOnline helpComputerAlgorithmData structureRevision controlInfinityCodeCartesian coordinate systemResultantSet (mathematics)Descriptive statisticsSlide ruleBasis <Mathematik>Arrow of timeInformationMeasurementFinitismusConnectivity (graph theory)Latent heatTheoremInverse elementCodierung <Programmierung>Quantum computerTouchscreenTuring-MaschineQuicksortTuring testDifferent (Kate Ryan album)Virtual machineObject (grammar)Uniformer RaumDimensional analysisScaling (geometry)Fourier transformFehlererkennungQuantum information scienceEnergy levelComputer simulationRow (database)Local ringGame controllerSinc functionGoodness of fitLibrary (computing)HolonomiegruppeBit rateCodeStability theoryLeakDatabase normalizationBit1 (number)Source codeIndependence (probability theory)Operator (mathematics)Two-dimensional spaceExecution unitMathematical analysisDemonPropagation of uncertaintySound effectCubeFigurate numberGame theoryQuantum circuitPropagatorSocial classPattern recognitionGraph coloringCASE <Informatik>DemosceneSummierbarkeitTowerThresholding (image processing)DatabaseConstructor (object-oriented programming)Computer hardwareComputer animation
20:03
Logic gateDegree (graph theory)Power (physics)Digital electronicsApproximationFinitismusRotationNumberLimit of a functionInteractive televisionInformationFourier seriesBitAlgorithmLocal ringQuantum computerDescriptive statisticsFunctional (mathematics)Compilation albumSequenceMultiplication signSpeech synthesisLoginOrder (biology)LogarithmSimulationBasis <Mathematik>MereologyFault-tolerant systemPolygonProxy serverCopyright infringementQuicksortComputer simulationLecture/Conference
21:51
Grand Unified TheoryExecution unitFluidHill differential equationMIDIMoving averageLogic gateQuicksortBasis <Mathematik>Set (mathematics)State of matterCodeOperator (mathematics)MeasurementGame controllerComplete metric spaceInformationTheoremMultiplication signPhase transitionMereologyBitQuantum computerSurfaceHadamard matrixCodeImplementationDigital electronicsCodierung <Programmierung>Entire functionFinitismusUniverse (mathematics)Clifford algebraReal numberMilitary baseConstructor (object-oriented programming)Standard deviationDatabaseNumberAlgorithmInverter (logic gate)PlanningPositional notationCausalityComputerGroup actionFrequencyAngleBit rateACIDCopyright infringementEuler anglesDisk read-and-write headCategory of beingSpiralInversion (music)Classical physicsComputer animation
25:19
InfinityCodeCodeBlock (periodic table)InfinityError messageField (computer science)Electronic mailing listCodeStability theoryDifferent (Kate Ryan album)Sierpinski triangleAdditionData structureQubitFamilyLevel (video gaming)PhysicalismThree-dimensional spaceDigital electronicsWage labourFormal grammarFehlererkennungComputer animation
26:50
InfinityCodeCodeSpacetimeHomologieConnected spaceDifferent (Kate Ryan album)Closed setBoundary value problemFault-tolerant systemCodeComputer hardwareInfinityFormal languageTesselationFamilyGoodness of fitComputerThree-dimensional spaceElectronic mailing listTheoryCommunications protocolAreaStability theoryContext awarenessGraph coloringOperator (mathematics)Lattice (group)MeasurementNetwork topologyCollaborationismLocal ringThresholding (image processing)Denial-of-service attackDimensional analysisComputer animation
29:10
CodeFamilyInfinityCodeStatistical mechanicsFault-tolerant systemInflection pointRenormalization groupCodeWechselseitige InformationSurfaceCurveLevel (video gaming)Graph coloringThresholding (image processing)Reading (process)Asymptotic analysisFamilyRight angleNoise (electronics)Scaling (geometry)Endliche ModelltheorieFehlererkennungFunctional (mathematics)outputElementary arithmeticPoint (geometry)Physical systemFitness function1 (number)Goodness of fitPointer (computer programming)WebsiteComputer simulationBitComputer animation
31:29
Endliche ModelltheorieMappingEndliche ModelltheorieCodeLogic gateUniform resource locatorNoise (electronics)Functional (mathematics)BitMeasurementCodierung <Programmierung>QuicksortInvariant (mathematics)Phase transitionError messageParameter (computer programming)Artificial neural networkResultantStatistical mechanicsNatural numberEstimatorExterior algebraHamiltonian (quantum mechanics)Physical systemTerm (mathematics)MetreBinary multiplierThresholding (image processing)Identity managementGoodness of fitLocal ringWordSet (mathematics)Computer simulationSummierbarkeitStandard ModelGraphics tabletDigital electronicsProcess (computing)HypermediaCross-correlationDimensional analysisOperator (mathematics)Key (cryptography)Numeral (linguistics)Context awarenessNetwork topologyComputer animation
35:14
Execution unitDigital electronicsAdditionPolygonError messageOperator (mathematics)State of matterBitNumberQubitStability theoryCodierung <Programmierung>CASE <Informatik>Electric generatorLogic gateCodeGame controllerSound effectMultiplication signFault-tolerant systemQuicksortInformationKnotCross-correlationFehlererkennungBell and HowellCodeClassical physicsIndependence (probability theory)Pointer (computer programming)Process (computing)Single-precision floating-point formatTransverse waveBound stateNoise (electronics)Network topologyDistanceLevel (video gaming)CircleArrow of timeIdeal (ethics)Dirac delta functionComputer-assisted translationFraction (mathematics)TrailForceCommunications protocolComputer animationProgram flowchart
39:16
Theory of everythingExecution unitError messageCodePropagatorQubitBitVertex (graph theory)Lattice (group)Fault-tolerant systemArithmetic meanNetwork topologyCodeEigenvalues and eigenvectorsOrder (biology)Element (mathematics)Multiplication signDistanceData structureScheduling (computing)QuicksortGoodness of fitMereologyCommunications protocolStability theoryLocal ringMultilaterationRevision controlGame theorySurfaceFehlererkennungForceGame controllerEntire functionPropagation of uncertaintyCASE <Informatik>Execution unitCategory of beingMetreCubeComputer animation
42:38
Theory of everythingFormal verificationCodeMultiplication signHadamard matrixFormal verificationResultantDistanceState of matterGame controllerNumberFigurate numberProcess (computing)Communications protocolComputer-assisted translationType theoryLattice (group)Procedural programmingDifferent (Kate Ryan album)BitCodeError messageScheduling (computing)Degree (graph theory)Single-precision floating-point formatMereologyDigital electronicsLogic gateCodierung <Programmierung>Latin squareCellular automatonInformationDemosceneWordParticle systemEntire functionHypothesisForceComputer animation
46:07
Formal verificationExecution unitCodeMessage passingDifferent (Kate Ryan album)Data recoveryFormal verificationMathematical optimizationSoftwareExecution unitProgrammer (hardware)PropagatorMultiplication signIterationLevel (video gaming)Error messageComputer architectureObservational studyDistanceElectric generatorCodeForcing (mathematics)CalculationSurfaceSystem callAlgorithmLogical constantCollaborationism4 (number)GodComputerInformationComputer scienceCodierung <Programmierung>CASE <Informatik>Phase transitionThresholding (image processing)Matching (graph theory)LoginBitMappingLinear programmingGeometryComplex (psychology)Cross-correlationSocial classOrder (biology)Quantum computerProcedural programmingWeightPerfect groupLogarithmQuicksortNP-hardStability theoryPolynomialFault-tolerant systemEndliche ModelltheorieMaxima and minimaRenormalization groupScaling (geometry)Statistical mechanicsComputer animation
50:42
Quantum computerGoodness of fitCodeFault-tolerant systemCodeOperator (mathematics)QubitComplex (psychology)ResultantPlanningError messageUniverse (mathematics)Multiplication signAdditionLogic gateTransformation (genetics)Codierung <Programmierung>Strategy gameForm (programming)ComputerFehlererkennungProcess (computing)Block (periodic table)QuicksortWordTwo-dimensional spaceOcean currentPlotterInformationPairwise comparisonGame controllerComputer animation
52:22
12 (number)Logic gateIdentical particlesStability theoryLocal ringSpacetimeMeasurementOperator (mathematics)Transverse waveSystem callOptical disc driveThree-dimensional spaceQubitBitHadamard matrixMatching (graph theory)CodePhase transitionError messageLength1 (number)Digital electronicsQuantum computerWordSet (mathematics)Eigenvalues and eigenvectorsModulo (jargon)FehlererkennungCodeLogicCommunications protocolTheoremGame controllerQuicksortWeightCase moddingMultiplicationACIDMatrix (mathematics)Process (computing)Block (periodic table)Mechanism designLink (knot theory)Power (physics)Fiber (mathematics)State of matterSource codeSigma-algebraComputerEscape characterComputer architectureHypermediaStudent's t-testSingle-precision floating-point formatForm (programming)Computer animation
56:09
CodeHill differential equationQuantum computerSurfaceQubitLogicCodeState of matterService (economics)MeasurementInjektivitätLevel (video gaming)Web crawlerNoise (electronics)Communications protocolProcess (computing)Codierung <Programmierung>FehlererkennungComputer animation
58:13
Execution unitFault-tolerant systemBound stateComputer programmingThresholding (image processing)Quantum computerExtension (kinesiology)Endliche ModelltheorieMathematical analysisReverse engineeringTerm (mathematics)Digital electronicsNoise (electronics)Operator (mathematics)AreaOverhead (computing)Sinc functionCodierung <Programmierung>Numeral (linguistics)Form (programming)Game theoryRevision controlWordLevel (video gaming)Physical lawFile archiverEstimatorState of matterCopyright infringementPower (physics)Reading (process)Shared memoryType theoryRectangleGraph coloringLecture/Conference
01:00:58
Personal identification numberQuantum computerBitProcess (computing)AlgorithmConnectivity (graph theory)Communications protocolDigital electronicsOverhead (computing)Fraction (mathematics)View (database)Latent heatControl flowNumberAnalytic continuationIdeal (ethics)Nichtlineares GleichungssystemComputer architectureCellular automatonComputer simulationFocus (optics)Particle systemLecture/ConferenceMeeting/Interview
Transcript: English(auto-generated)
00:18
I'd like to thank Daniel and the other organizers for inviting me to give you a tutorial on
00:22
fault tolerant quantum computing. Like Todd, there's a lot of material to talk about in just one hour. Fortunately though, I have a bit of a release valve that Todd did not have. Robert Rausendorf will be speaking after me about how fault tolerance applies to surface codes.
00:40
And Daniel Gosman will be giving a keynote talk at the end of this workshop on Friday, also about fault tolerant quantum computing. So any of the topics that you don't hear about here, you may hear about in these other talks following mine. So because of that, I've structured this tutorial to really focus more on the of quantum
01:00
computing. You know, what comprises a fault tolerant quantum computing protocol? How does it work? And not so much on the analysis of fault tolerant quantum computing protocols, which is really a subject in and of itself. Okay, so if we're going to talk about fault tolerance, maybe we should define what fault tolerance is.
01:22
So fault tolerance is the ability to function correctly in the event of a failure. And like Todd mentioned, we typically aren't able to handle every possible failure, but a certain set of failures. It's important to realize not only that, but also to understand what the process is. If you actually bother to read these end user license agreements on your software,
01:44
you'll notice some of them say this software is not fault tolerant, not intended for aircraft, you know, navigation or nuclear power plant, you know, you know, software. Those are things that you want to be fault tolerant. What's the process as opposed to it's not getting you from point A to point B, it's
02:02
not killing you. So it's important to know, you know, that the failures which, you know, an airplane is supposed to be fault tolerant to isn't necessarily getting you to a destination, but to protecting the cargo inside. So a more mundane example is just to protect the data, to protect information, it could be classical or quantum.
02:22
And if that information is supposed to just be static, we say that's protecting a memory, it's just staying there. But if we're trying to get the information from point A to point B, then we say it's communication. We're trying to protect communication. And the failure set that we're going to think about is a very narrow set, just the corruption of the data itself, nothing else.
02:40
And coming from let's say local environmental noise. So it's not adversarial, it's just some sort of local noise source. And there's a solution to this, which we just heard about, error correction. It works classically, it works quantum mechanically. And the solution involves adding layers of redundancy and extra processing in order to achieve. And we're assuming, again, that those processes in the error correction setting are themselves
03:04
ideal. So the only faults that we're worried about are corruption to the data. And so this process for that narrow failure set is in fact fault tolerant. We can lower, we can suppress the failure probability in data to whatever level epsilon we desire by using a code that's sufficiently large, it has to be order log of one over
03:25
epsilon large, to protect the information. That'll work as long as the error rate per data satisfies some criterion, an error threshold. So if we have a local noise model where each bit, say, flips with probability p, then
03:40
as long as that bit flip rate is below some critical value, which I'll call the error threshold, then it is possible by using a larger and larger code in a certain family to suppress errors arbitrarily well. So error correction is itself a fault tolerant process to a very narrow error set. But if you think about this a little while, you realize that this isn't completely satisfactory
04:02
because a more realistic model should account for failures in the processing that's itself used to protect against those errors. That's a really natural thing to consider. Moreover, we can get a little bit more greedy and say, well, now that we've protected the information very well, we want to actually do something with it.
04:20
We don't want to just have it sit there. We want to build computers, not just hard drives. And so we'd like to be able to process the information in a coded form. It's not a good idea to decode the data, process it while it's exposed to noise, and then re-encode it. That doesn't seem like a particularly robust way to do things. So generally, we use the expression fault tolerant quantum computing to refer to protocols
04:43
that work arbitrarily well or efficiently also in the presence of faults to both its data and its processing. And two of the central questions overall in the field of fault tolerant quantum computing are exactly the computation models, control models, and noise models that will admit
05:01
fault tolerant quantum computation. We actually only know a very narrow class of combinations of these models that will allow fault tolerant quantum computing, despite that there's quite a large body of literature in the field. And it'll be interesting to understand if nature admits other combinations.
05:21
The other essential question of the field, I would say, is what are the resource costs for achieving fault tolerant quantum computations? So it's one thing to say that it's possible. There's another question to ask, well, just how difficult is it? It would be particularly exciting if nature had discovered a way to do it by itself. Okay, so before I launch into fault tolerant quantum computing, let me spend a moment
05:41
talking about fault tolerant classical computing, something which even some of the, I think, quantum computing experts might be less familiar with. So modern computers, as we all know, are very reliable. They can calculate for weeks or maybe even years. I've certainly run calculations that lasted months, but nothing ever that's run by somebody here in the audience has. But they're very reliable.
06:00
And it's not because that the hardware is particularly fault tolerant. It's just that it's very good. The error rates are so low in these things that in a time scale of a computation we're interested in doing in our human existence, it just doesn't fail. However, we could, we know that in principle it is possible to do classical computation even with faulty hardware.
06:20
And I think we're beginning to enter a new age in classical information processing where this is an acceptable way of doing computing. You know, there's demands to use less power in our cell phones and our smartphones and things like this. Or to save money, if you're a business, you might find that it's cheaper to build lousy hardware and hire a couple of engineers to make it work right than it is to build
06:40
better components in the first place. So it's possible that fault tolerance, you know, will sort of have a revival, I think. And we're starting to get to that point as we're getting these parts very small. Fault-tolerant classical computing will begin to come to the fore again for unfortunately not great scientific reasons, but probably for economic reasons. In the setting of classical computing, we'll narrow it again here. We'll talk about circuits and more specifically formulas.
07:02
So this is a narrow class of circuits where each gate in the circuit has a single output. So for example, AND, OR, NOT gates, things like this. And the control model is that we're going to admit parallel operations. So we'll allow AND and OR gates to happen at the same time, say, and we're also going to allow ourselves to refresh bits.
07:22
This is a very key assumption. If noise is being introduced to our system, it's generating entropy in our system. We need some means for expelling it from our system if we're going to try to protect it. And so we're assuming that we have some mechanism for doing that classically. And our noise model is going to be very simple for this computational model.
07:40
We'll say a noisy gate looks like an ideal gate, and then it'll be followed by a bit flip with the probability p. And so that's the setting that we have. And the approach for fault-tolerant classical computing is to simulate this ideal formula with a faulty formula. And you want to simulate it to the desired precision. So that's one of the key ideas I'd like to get across in this tutorial is that fault-tolerant
08:02
quantum computing is really all about simulation. It's about simulating an ideal process with a faulty one. That's sort of the overall guiding principle. It's not about computing in its own sake. It's about simulating something that you'd like to have happened, but it didn't happen. And the second part of this approach that I'd like to get across is that the way
08:22
we do this simulation is to structure it so that it suppresses error spreading. That's the key idea. How do we simulate something well? We simulate it well by making sure that when errors do occur, yeah, maybe they grow a little bit, but they don't sort of grow catastrophically and cause the entire simulation to crash. That's something that we'd like to avoid.
08:43
So there's this celebrated threshold theorem for fault-tolerant classical computing by von Neumann starting in the 50s, and he's had extensions of that all the way through the 60s, that says that it is, in fact, possible to simulate an arbitrary formula with g gates to precision epsilon by just using logarithmic overhead.
09:01
So an order g log g over epsilon gate faulty formula. And again, there is a criterion, a caveat here, as a function of the noise model that says this is possible whenever that the error rate is below a critical parameter. In this case, I'm going to call that the accuracy threshold to distinguish it from
09:22
the error threshold that's used in just straight quantum error correction. So if you're familiar at all with this area, you might think, well, this is kind of a dead field, you know, it's been many years since people have studied this, and, you know, the hardware's all really good, so why would we care? Theoretically, it's interesting as well. There have been recent developments exploring the prospects of fault-tolerant
09:44
classical computing. It's only in 2008 that we've learned that the threshold for fault-tolerant classical computing, if you restrict all the gates to just have two-bit inputs and one-bit outputs, is 8.9%. So, and that's tight. So that's the best you could do in this format, in this model here.
10:01
So when you hear people discuss thresholds for fault-tolerant quantum computing of, you know, 10 to the minus 3, 10 to the minus 4, whatever, bear in mind that in fault-tolerant classical computing, it's 8.9% is the best you could do with faulty classical components. I should add also, though, that just because this is 8.9% in principle doesn't mean that fault-tolerant quantum computing couldn't have a higher threshold because
10:24
we typically assume that the classical computing that augments a quantum computation is itself ideal. You might imagine some clever scheme which could somehow dump all of the errors into the classical computer, and then since we're artificially assuming the classical computer is perfect, could boost the threshold. But it seems to be unlikely. So I'd say this is, while not a strict barrier or strict upper bounce to the
10:44
threshold for fault-tolerant quantum computing, it's likely you're not going to find a quantum computer with a threshold higher than this. And if you allow yourself to have gates that have inputs greater than, like, 3, 5, 7, etc., then actually you can push the classical threshold all the
11:01
way to 50%. You know, you can asymptotically approach that. So we can get very high thresholds for fault-tolerant classical computing if we increase the basis of gates that we're allowing. Okay, so that's fault-tolerant classical computation. What about quantum computation? So we need to define the setting here.
11:20
The first thing we need is a computational model. And right now, as things stand, there are four computational models that are known for quantum computing, and they all have variants of them. There's the first three, the Turing machine, walk, and adiabatic models. They're not known to be fault-tolerant. They're interesting. The Turing machine is sort of more of an academic one.
11:41
It's the only model that's really self-contained. The other three models require a classical Turing machine to construct uniform families of objects in them. So the quantum Turing machine is the only self-contained quantum computational model we know. That's kind of interesting. The walk model, it's not known to be robust. It's likely to be subject to Anderson localization that Landauer mentioned, I
12:01
guess, in our recording of the introduction that we saw before we heard about this. There might be ways around that. The adiabatic model has a lot of intrinsic robustness to noise from the way it's, you know, it's gap protection and certain control robustness, but it's not known to be fault-tolerant. The only thing we know to be fault-tolerant is a circuit model.
12:20
This is the model where we take an arbitrary computation and we decompose it into these elementary pieces, and we make each of the pieces good and put them back together again and make the computation whole. And those pieces might be implemented in ways that are either topological or through holonomies or through local measurements or whatnot. But that's what we're working with. So from here on out, I'm going to be restricting the circuit model.
12:42
In the control model, there are a number of assumptions that are made in fault-tolerant quantum computing analyses. I've color-coded these here for ones that are either necessary, helpful, convenient. So in the control model, parallel operation is actually provably necessary
13:02
for a fault-tolerant quantum computing protocol. If you're fixing errors over here and you let things over there fall apart, by the time you get over there, they'll fall apart. You have to really keep on top of the whole system at once in order to have any hope of keeping it from crashing. Keep in mind, you don't need perfect parallelism. You don't need to have the maximal parallelism possible.
13:21
Maybe every 10 steps, you get to look over here, and that will impact the performance of the protocol. But you need to have some degree of parallelism. You need a way to dump entropy. Again, that's provable. You have to have a way to refresh your qubits in this case. It's convenient to assume, what do they call it? Helpful. It's helpful, sorry, to assume that you have fast classical computation.
13:41
So instantaneous, if you like. It's not necessary. In fact, it's probably not even realistic. I mean, you're probably going to push our quantum computers as fast as our classical electronics can go. It's, but it's a, you know, it's a theorist's, you know, delight. You know, put these helpful assumptions in, and you can take them down in their thresholds, theorems for that one that's relaxed.
14:01
We have a finite, a specific finite gate basis. So we typically pick one. It might actually be necessary to have a finite gate basis of some kind. I don't have a theorem that says that, but it seems plausible. But what I mean by this is that we assume a particular gate basis. So when we do an analysis, we pick a gate basis and say, this is the one we're going to use.
14:23
Moreover, we assume that each of those gates have an equal amount of time. This is, again, typically not realistic. Measurements in a hardware, you know, often have a different time scale than the coherent gates, say. Two realistic assumptions, though, that are worth considering is a 2D layout. So many quantum technologies are naturally laid out in two spatial dimensions.
14:42
And so that's something to think about when you think about locality. In particular, it's plausible to believe that all of the quantum processing that's realistic to do can only occur between information that are relatively close to one another. It's unlikely to imagine that you could do something between two parcels of quantum information that are distantly separated
15:01
as easily as you could if they were close together. For a noise model, it's necessary to have a non-increasing error rate. If the rate of errors in your system grows as the size of the system grows, then you're fighting an ever-growing demon, and there's no hope of ever catching up with it.
15:21
So you need to make sure that it's not increasing as you grow, or at least it's not increasing at the same rate at which you could possibly put redundancy in to correct it. It's helpful to assume that the classical computation that augments the protocol is not only fast but reliable.
15:40
And also that qubits don't leak. So we'll assume that our qubits are there and they don't just disappear. It's helpful to assume that the noise is uncorrelated, that each qubit is its own independent noise source. Again, we can relax this assumption. And finally, it's convenient to assume that the noise doesn't depend on the state of your system.
16:01
So if your qubit is encoded in a one versus a zero, in a real hardware, you might think that it's more exposed. If it's in a higher energy state for one but not for the other, you might think that there's a sort of state-dependent noise. We're not going to assume that. We're going to assume that the errors are a function of the gates and the operations, not of the states themselves.
16:20
And we'll assume that the gates are uniformly faulty. So if I do a CNOT gate now and then I do a CNOT gate an hour from now, I'm going to assume that it's going to have the same failure model, which again isn't necessarily the case, but it's a natural assumption to make. So there are all kinds of assumptions. And I guess the main message from this slide is that whenever you read a description of a fault-tolerant
16:43
quantum computing protocol in the literature, keep a watchful eye on what the set of assumptions and the models involved are, because they can change the results dramatically. Okay, so let's talk about fault-tolerant quantum computing, like in applications.
17:00
So suppose we want to simulate a particular circuit. So in this case, I've got, I guess it's an inverse quantum Fourier transform. I know it's not particularly legible, but there's some circuit you'd like to simulate. Every fault-tolerant quantum computing protocol that we know of has four components to it. Maybe there's other ways to come up with it, but right now we just know four,
17:21
and they themselves can be broken into two pieces. Oops, I'll move this arrow here on the screen. So we have a fault-tolerant quantum error correction protocol and then a protocol for doing encoded computation. And the error correction protocol has three pieces. We have an infinite family of codes, a protocol for extracting the syndrome from each of the codes.
17:42
This is implicitly assuming we're doing stabilizer coding or syndrome-based decoding. A decoding algorithm for interpreting the syndrome. So once we have all this classical information, it tells us what the syndrome, how do we infer what the errors are given that. That's a classical protocol. It's called decoding for historical reasons. It doesn't mean unencoding,
18:00
like doing the inverse of the encoding circuit. It just means inferring the errors given the syndrome. And then a finite gate basis that's universal and a way to implement each of those. So when we have these four pieces, how do we actually affect a fault-tolerant quantum circuit? Well, the first thing we do is we take our ideal circuit, this thing here,
18:20
we compile it into a circuit over our gate basis. It'll get a little bit larger when we do that. Then we choose a code that's large enough to suppress those errors below one over the size of the new circuit with fault-tolerant quantum error correction. And so in order to know what, the algorithm dictates the size of the code we use.
18:41
If you have a really big algorithm, you go to your infinite code library and you dial a big enough code to handle that. And the fault, the protocol is designed to not propagate errors badly. So you just need to suppress errors to one number of gates. You don't have to worry about the spreading of the errors in that circuit. Once we do that, then we replace each of the gates in the circuit. We've chosen the code.
19:01
Now we replace all of the gates in our compiled circuit with the encoded versions of it with this code. And after each gate, we insert a syndrome extraction. Some of them might be able to be omitted depending on the structure of the actual algorithm. And we instantly know because we have the instant classical computational model,
19:21
we instantly know the decoding after the syndrome extraction, but we don't actually apply it all the time. That itself could be faulty. So we only apply it when we need to, which is before each non-Clifford encoded gate. You heard in the previous talk what these Clifford gates were. And at the very end, we do a measurement. We do a logical measurement of all the information.
19:41
We do classical decoding of the final outcomes to infer the result, because although the fault-tolerant quantum computing protocol is keeping errors from propagating badly, when they get to the very end, you keep errors in that very final time step. What you can do is classical error correction, since you're assuming the classical computer is ideal, to suppress the failure rate in that final measurement.
20:03
Okay, so let's go through these steps in a bit more detail here. So quantum compiling, this is our first step. So here's our inverse Fourier transform circuit. And so you can see that there's these rotations here by pi over two, pi over four, pi over 32, et cetera. If you had a really big Fourier transform,
20:21
you can imagine to have really teeny tiny rotations here. And if you have a finite gate basis, you're not going to have all of those. So we compile it. And the degree to which we want to compile it is, well, the compiling itself is a simulation. We can only approximate each of these gates to some precision. And you might ask,
20:41
well, how well do I have to approximate each gate in this circuit? That itself is a function of the overall circuit itself. So that's one of these places where global and local information interacts. You need to know the whole circuit, the number of gates in the entire circuit to know how well you need to approximate each gate in the circuit with this quantum compiling. So if there are G gates total in the circuit, you need to simulate it with your quantum compiling
21:02
to order one over G. So the Solovay-Kitaev algorithm guarantees that we can do this and do it very well. There's a particular explanation by Dawson and Nielsen. They have a variant of it that's very nice, where you can actually, if you're given a gate U, you can find an approximation and you want to get an approximation,
21:20
epsilon approximation to it. You can do it in log to a power of one over epsilon. You can actually find the approximation sequence in a time faster than the sequence itself because the description is compressed. And so when you do this, we go to compile the circuit. If our original circuit had G gates and then our new one has polylogarithmically more gates
21:45
in the new circuit. And this is the circuit that we're going to simulate fault-tolerantly. So this is our first step. Now we have to choose a gate basis. So there are lots of finite gate bases from which to choose. So if you're the kind of person that likes to keep it real, there's a real gate basis.
22:01
You can use the Hadamard and the Toffoli. Heoye and Xi showed that this is a universal gate basis. Of course, we augment it with the ability to prepare and measure states as well to get a sort of a complete gate basis, not just the coherent part. If you like the Hadamard gate and want to just add a two-cubic gate, Kataev showed you could add the controlled S or phase gate to the Hadamard to make it universal.
22:22
You'll be hearing in the next talk by Robert that the surface code cluster state gate basis, you can have a controlled phase, controlled Z gate Hadamard, and some preparations and measurements and an unusual measurement, actually, augmented with these to get universal quantum computing. In all of these, though,
22:40
the one I think that's most discussed in the literature, I'll call the standard gate basis, it's the Hadamard gate, the T gate, or so-called pi over eight gate. It's the pi over, about the Z axis by pi over four, but because of the half-angle formula, it's pi over eight, and a controlled NOT. It's convenient to actually use NOT. That's a very parsimonious basis.
23:01
We can expand it, include all of the gates and their inverses, and that's useful for the quantum compiling algorithms, which typically require that. So there's this more over complete one. I'd say a favored gate basis in fault-taunt quantum computing constructions is this latter one here, where the only coherent gate we have
23:22
is the controlled NOT gate, and everything else is preparations and measurements. So this first collection of operations is what we call the CSS set of gates. These are gates that have particularly nice implementations for CSS codes that I'll be describing later. We can add preparation of the so-called plus i state,
23:42
zero plus i one. I've got a little legend up here for those of you not so familiar with this notation. It's a bit congested here as well. If you have difficulty understanding me, please ask for clarification. Adding this plus i state allows you to get the entire Clifford group
24:01
in encoded form, and then this t state allows you to do the t gate and get universal quantum computing. So this is great, but to actually use it, well, there's a couple of things to realize. One, we don't have x or z gates, but that's okay. We can propagate those forward. There's this Gottesman-Nill theorem that tells us that we don't actually need to know those.
24:22
We can just keep the information in our head and propagate it forward. And to do the s, t, and h gates, we can do it with these so-called magic states. So this pi over two state, which is the same as plus i state, we can use that and the other operations. Again, we don't actually need the z here. To affect the s gate
24:42
and using this pi over four state or the t state, we can get the t gate and the plus state you can think of as a magic for the h gate. So we're able to, any time then in our original circuit where we had an s or a t or an h, we have to add this extra layer of circuitry and it blows up our circuit that much larger still.
25:02
I have this little warning here is that you might think that this is a Clifford circuit because s is a Clifford gate, but the classically controlled s gate is not a Clifford gate, even though because a single bit flip on the classical control will cause the s to not operate correctly. Okay, so we've got our circuit, we've got it compiled.
25:24
Now we need to pick a code. Well, for that we need an infinite code family. We need to go large enough to get the right code. And well, one way to get an infinite code family is to just pick a code and concatenate, concatenate, concatenate, concatenate. And so you can get some elaborate structure like this three-dimensional Sierpinski gasket
25:41
with wheels within wheels kind of thing. And there are many, many such codes that have been studied in concatenate literature. We know that you can use any stabilizer code as a base to concatenate, but these CSS codes, which you heard about earlier, particularly DICE, the lingo that gets used in the field is we talk about different levels of concatenation
26:01
where the zero level is the physical level of qubits and each higher level is another layer of encoding on top of that. A neat thing about error, about concatenation is that error detecting codes are handy in this scenario because although error detecting codes, they can only detect errors, they are able to correct located errors.
26:22
And so if you have concatenation and something, an error happens, is detected on a lower block, the block where the error is detected is now located for the higher level of code and that error detecting code can correct that. So there's a large role for error detecting codes in addition to error correcting codes in concatenation.
26:42
And I won't belabor this full list of codes, but there are quite a few here and pick your favorite and concatenate away. Now, instead of taking your codes and concatenating them, you can tessellate them instead. This is another way to get an infinite family of codes. There are many ways to get infinite family codes, but these two, I think, are the most widely studied.
27:02
So you can tessellate the code by thinking of it, laying it out in space and then thinking about how you can glue it together to get larger and larger codes. And the goal in doing this is to keep the checks, the language I use for stabilizer generators, so that it's a lot easier to say, to keep the checks local.
27:21
So you want to measure local checks, but have the logical operators be global over the entire area in which you've tessellated. So strictly speaking, these are homological codes. So homology is the theory of boundaries. And so the idea here is that the logical operators in these codes are boundary lists, and the checks are themselves boundaries,
27:42
like little faces or something like that. And so there's this close connection between homology and topology, so they're also logical codes as well. I think maybe that scares a lot of people off. If we call them tessellated codes, maybe they wouldn't seem so frightening. And so you can do this kind of tessellation in one dimensions, two dimensions,
28:01
three dimensions, whatever you'd like. Naturally, we're focused on two dimensions, although there are some hardwares that work in 3D and some that are stuck in 1D. Not all such codes are good, so I'll show you later. The bacon short codes, you can imagine putting on a very large lattice, but they don't perform well themselves as fault-tolerant computing or codes
28:21
for fault-tolerant computing protocols. They're good for a base code that you can concatenate, but if you just thought of them as an infinite family of codes on larger and larger lattices, they don't have a threshold, so that's not good. So here's, again, a list of codes that I'm aware of, and I'm sure there are more, for tessellating a code in space to come up with an infinite family.
28:44
Incidentally, these three codes here, these color codes, they start with ode, and they tessellate them in three different ways, so it's another way to grow an infinite family code from a steam code than just concatenating it. And this code here, this is from Hector Bamben, a collaborator,
29:01
how to do a three-dimensional color code it's just the same as the 1513 Reed-Muller code. Okay, so how well do these codes perform? Well, typically what we look at, we look at what's the failure probability of the system or the code
29:22
as a function of the input probability per elementary data, piece of data, let's say. And if we concatenate the codes, then we find that as we increase the code size, these curves, they start to become steeper and steeper and all intersect at the point, roughly where they line p equals p fail.
29:40
Now it drifts a little bit, so we call this, you know, any particular point a pseudo-threshold, so we talk about a level one threshold, level two, etc. And I'd say, I think it's fair to say that we don't really understand well how that drifting occurs, so for people who do numerical simulations, they report a value as a pseudo-threshold, but they don't, it's hard for them to know exactly
30:00
what that means asymptotically. Surface codes and color codes have the feature that the codes intersect at their mutual inflection point, not at the point where they intersect p equals p fail. And so that means that they continually get better and better and better as they go up the threshold for any particular finite sized surface
30:21
or color code increases, but it asymptotes at the, wherever the level of the mutual inflection point is. The bake and short codes, the example I mentioned earlier, they too get steeper and steeper, and they start getting better, they start moving forward like the surface and color codes, but then they start going retrograde and they start going down, down, down until the threshold goes to zero.
30:41
So not all infinite family of codes are good, you have to think about them and study them to see which ones are, which ones are not. To find what the threshold is, you know, you can look at, you can try to find these intersection points. It turns out for the surface and the color codes, there's this statistical mechanical ansatz you could make
31:04
to know what the scaling is going to be like near the intersection point. So you don't have to search for a crossing, you can sort of fit to a scaling that comes from a universality class in the stat mech model. And a warning here is that these curves look the exact same for error correction as they do for fault tolerant error correction.
31:22
And so when you read a value for a threshold, you know, just be very careful that you're reading it for the right kind of noise model. Actually, maybe this is a good segue into noise models. What are the noise models that people think about? The natural one to start with is to say, well, let's imagine the depolarizing noise model.
31:40
So we'll assume that each, each gate preparation and gate is ideal followed by the channel of a function of P. Let's say it'll be the parameter describing it. I will assume each measurement is preceded by that depolarizing channel, and we'll also flip the result with probability P. We need to do that last step because, just because if the depolarizing channel flipped a bit
32:03
and then we measured it, it would say that measurement's correct. It reflected the actual value of the bit that got flipped. So to make the measurement itself fault, we have to imagine the meter itself can fail independently of the data failing going into the meter. So that's a natural noise model. It's one that's used in numerical estimates quite a bit.
32:22
An alternative one is to assume that instead of the depolarizing channel, we have the bit flip channel followed by the phase flip channel, or preceding it for each of these operations. So what that means is that a Y error is actually less likely because it would require an X error and a Z error to happen.
32:40
There are correlations in it. There's a phenomenal, I'll call it a phenomenological error model where we don't look at the details of the circuitry that's used to extract the syndrome. We just say that each one of those bits that we measure is just failing with probability P. It's not a particularly realistic model, but it is what allows us to do this mapping onto the stat mech model for those topological codes.
33:05
And something to be aware of is that decoders are a lot, for CSS decoders, because you have X checks and Z checks, it's natural to say, well, one of them looks for bit flips and the other looks for phase flips. And so I'll just do decoding classically on each of these. You can do that, but if you have the depolarizing channel,
33:21
you're missing the fact that X and Z errors are more correlated, that it becomes more likely for an X and a Z to happen together than for them to happen separately. And so that kind of decoding is not really optimal for the depolarizing channel, and you have to have a more subtle decoder for that. But for the bit flip channel followed by the phase flip channel, it is optimal. And so in the literature, again, you have to be careful when you read these things.
33:41
You might have to multiply threshold values by two thirds to compare one value to another. You just, that's the way you would map between those two channels if you were to decode this way. So again, caveat emptor. While those are nice models to use for numerical simulations, they're not necessarily easy to analyze analytically. And so in this model,
34:02
in this setting, we will sometimes just look more generically when it's called local stochastic noise, or we just say that if you have our specified locations in the circuit, so these are, a location is where a gate is. A gate could be the identity gate, or it could also be a two cubic gate, or a preparation or a measurement. In each one of these locations, some of the probabilities of all fault paths,
34:23
so collections of faults with faults at those locations is no larger than p to the r. That's very generic, and it doesn't, it's not assuming independent noise on each of these. Why would you possibly want to look at a noise model like this? It's so artificial. What's nice about it is that it's invariant under concatenation. So if you're trying to study how concatenated codes work,
34:40
it's very nice. It's got this sort of, it's invariant through that process. You can also generalize to non-Markovian noise, where it's a bit more realistic where you have a system bath Hamiltonian. You can make that local or non-local. You can have system bath terms just wherever the gates are. You can make them happen wherever. And there have been plenty of papers,
35:01
you know, looking at these generalizations. And so, again, it just depends on the setting you're at. It's which noise model we're going to consider. I'm going to, for the rest of the talk, think mostly about like these depolarizing noise channels. Okay, so now we want to extract the syndrome. So we've got our code. We've thought about the noise. How do I extract the syndrome?
35:22
Well, I need to measure these poly operators, these stabilizer generators or checks. There's a generic circuit that will allow you to do that for a general poly operator. But it's not particularly fault tolerant. If you, for example, even had ideal gates and you have a bit flip here that happens in the middle of a circuit that's intended to extract the poly operator x, x, x, x,
35:41
then the x operator, the failure that happens in the middle will propagate through the control knot and create a correlated error in a pair of bits here. And that's not good. We don't want errors to grow. We want to keep them sort of bounded. And so, there are at least four possible solutions to this debacle.
36:00
There's shore extraction, steam extraction, nil extraction, topological extraction. So I'll talk about these in turn. So the shore extraction method, what we do is, we extract the syndrome bit by bit and for each bit of the syndrome that we want to extract, we prepare a so-called cat state. It's a state in the repetition code that's the logical plus for the repetition code.
36:23
And it'll work for every stabilizer code. So any stabilizer code you have, you just, for that bit of syndrome, you extract it this way. And it turns out that to increase the reliability of the syndrome value that you extract, you need to repeat the extraction a number of times equal to t plus one,
36:40
where the distance of the code is d equal to 2t. So this works, but requires some repetition. A little bit more efficient way of doing things is to use steam extraction. So this will, unfortunately, only work for all CSS codes, unlike the shore method, which works for all codes.
37:00
And what you do is, you create an ancilla that's not a cat state, but a state in the code in which you are trying to extract the syndrome from in the first place. So you double the number of qubits in this case. And you transversely, so do CNOTs between the data that you have in the ancilla,
37:21
and the CNOTs either go up or down, depending on whether or not you're extracting a Z check or an X check. And then you destructively measure the ancilla, and do classical decoding on the outcome that you obtain. And if you push through this, you'll see that it has this neat effect that it won't propagate one error to two anywhere here. If there are no correlated errors in this ancilla,
37:42
it doesn't create correlated error anywhere. And you will not disturb the data any more than just learning the information about the syndrome bit that you're interested in. So that's a nice technique. You can be even more efficient at the expense of using even more qubits
38:00
by using an encoded Bell state in the code, not just the encoded plus or zero state. This is the nil extraction technique. And what you do is, in a single transversal operation between the ancilla and the data, you learn both the X and the Z checks in parallel, so like in a single step. Turns out you also teleport the data
38:21
to the other half of the encoded Bell pair. And you can imagine even having these Bell pairs be pre-loaded with the gate you want to do. So in addition to doing error correction, you can be doing an encoded gate at the same time. So that's pretty cool that in a single step, you can be doing error correction and an encoded gate. And like the previous protocols,
38:41
at most one data error will propagate data error. You won't get correlated errors. However, if there are correlated errors in any of these ancilla states, then they could propagate badly. So we need to ensure that we don't have correlated errors in the ancilla. And so that will be a distillation process that I'll talk a little bit more about in a bit.
39:00
And I should say that if you have a concatenated code, you will do this error correction at each level independently. So you're able to parallelize this whole extraction process a great deal with concatenated codes. Okay, topological extraction. So there's this obsession
39:20
of concatenated codes of keeping errors from propagating. But the topological approach is a little bit more laid back. It says, well, you can let the errors propagate a little bit just as long as they only propagate out to a finite distance and then stop. So it's more thinking about the global structure of the code that will prevent the codes from propagating badly, not some sort of local structure that keeps them from propagating badly.
39:42
So, and the nice feature of this is that the structure of the code is what's preventing the error propagation. And you don't need any elaborate ancillas. And that's a huge deal. It turns out that this ancilla business is extremely complex and consumes a large part of a fault tolerant protocol. So the two criteria you need
40:00
are that the code checks propagate to themselves and the syndrome checks propagated themselves multiplied by stabilizer elements. Let me give you an example of this. This is the surface code. You'll be hearing a lot more about this later. This is the version where the qubits are on the vertices. Kataev drew the qubits on the edges, but, you know, let's face it, qubits, they like to live on vertices. So I'm putting them on vertices.
40:21
So, and we've got a two colored lattice here. And for each blue color, we have a check that it's a Z check. And for each yellow one, we have an X check. So we measure, you know, it's X, X, X or Z, Z, Z around the faces. And so we either see not in, there's a syndrome bit at the center of each face,
40:41
and we either control not into that face to do the syndrome extraction. We don't do it fault-tolerantly. We just do it, you know, transversely like this. And so that'll mean that errors will propagate. But the neat thing is, if you look at the, if you have a stabilized generator here, in this case, it's Z, Z, Z, Z, and you ask, how does it propagate through this schedule, which is a clock schedule,
41:01
where it says at time step one, we do a C naught, let's see here, we do a C naught from this qubit to the central qubit. At time step two, we go from this qubit to the central one. Three, we go from here to the center, and four, we go to the center. So if we go around each face clockwise, then it will propagate that schedule and do that over the entire lattice. It'll propagate this stabilizer element, Zs,
41:23
it'll propagate through the C dots just to hitting each of the syndrome bits on the X checks twice, which would be no error at all. So the code check is propagated to itself. It doesn't, nothing's detected here, so that's good. But this schedule is a bad schedule. I mean, I have to admit, this is one I had on a paper I wrote a while ago.
41:41
It's not a good schedule for doing a fault-tolerant error correction, because if you look at the syndrome check, so if I look at, well, what happens to this bit here? So in the center, it's a zero. It's an eigenstate of Z. How does a Z propagate outward from here? Well, it'll propagate outward and be detected as two independent errors
42:01
by the X checks. And so that's not good. And so a smarter thing to do is the book schedule, where we have a schedule in book order. We do the C dots one, two, three, four on each of these faces. And if you do that, you can push it through and see that errors, which are not errors at all, just stabilizer elements
42:21
acting on the syndrome bits don't propagate to errors. So there's some, you have to do a little bit of thinking with these lattice and tessellated codes. But if you do it right, you can keep errors from propagating badly and avoid this whole ancilla game. One thing you have to do in topological code
42:41
is repeat quite a bit the syndrome. So we want to make sure that the syndrome is as reliable as the information, the data itself. So we repeat the syndrome extraction time a number of times equal to the distance of the code. It's kind of like having a repetition code in time. And so that boosts the reliability of our syndrome to the same degree as which the code itself
43:01
protects the information, which is the, let's say, the linear size of the lattice that we're using. That's in difference to the concatenated coding approaches, which only need a single syndrome extraction. However, there's a lot of post-selection because as you'll see in the ancilla distillation, you have to repeat many times.
43:22
Okay, so let's talk about this ancilla verification. So in the concatenated coding approaches, one way you can do that is Shor verification. So we could verify each syndrome bit separately on a state that we prepare to be
43:40
a logical plus state. So, you know, we want to see that it's reliable. We treat it itself as a code word. And if it happens to be a cat state, then all we have to add is a single CNOT gate. So for example, here this circuit in B, this is a figure from Brian Easton's thesis. He's got, you know, you do a Hadamard and some CNOTs
44:00
that would prepare a cat state. You add one more control not and that will verify. You measure that and if it's, if you get a one, that means you prepared a cat state on these three. If you get a zero, then you didn't and you try again. And so you just keep repeating until you get there. This is a slightly larger cat state. And if you had a code that was not a cat state,
44:22
then you would just do the syndrome, the Shor type extraction on it and using cat states themselves that had been verified. And so you can get a kind of elaborate procedure for verifying ancilla this way. And this part here, by the way, is the ancilla. This is just the preparation circuit coming from the generator
44:41
of the steam code that's making this state. Another way of verifying the ancilla is to not do it bit by bit, but do the whole thing at once. So you can actually, if you just have a distance three code, you can prepare a pair of encoded plus states,
45:01
check them for Z errors against each other. And if they both pass, then check them for X errors against each other. This works for a distance three code, but it becomes more elaborate if you have a distance D code. For example, here's a result for the Golay code that's a distance seven. This recursive procedure of verifying and verifying again becomes kind of elaborate.
45:22
But the nice thing about this is that you don't have to, you don't need to do this for each bit of the syndrome. You do it just once for the entire state that extracts the entire syndrome. There are many other verification protocols that have been developed since then. I don't have time to go over all of them. Some of the ones, there's a clever variant
45:41
using Latin squares that will force errors to not propagate badly and compress the schedule for verification. You can use ancilla decoding where you can remove the whole verification step if you think about the entire process of how you do syndrome extraction as a whole. There's an overlap method
46:01
that has been recently developed by Reichardt and Petsnick to exploit overlaps in stabilizer generators. There's all kinds of techniques to improve this, and this is just a tutorial, so this is sort of research-level literature. If you want to learn more
46:20
about those, I encourage you to read those. Generally though, the whole ancilla verification business, to give you a sense of how dire this is for fault-tolerant quantum computing, there's a somewhat recent paper that estimates that 68% of actual architecture designed for doing fault-tolerant quantum computing
46:41
is dedicated to just this whole ancilla pipeline. So if you're trying to compute, if you spend most of your time just trying to prepare ancilla, it seems like, oh, I don't know, you're not doing what you want to do most of the time. Okay, so decoding. So now we've extracted the syndrome. We're supposed to figure out what do we do with the information now that we have it.
47:02
Generally, if we assume that classical computing is instantaneous, we don't really worry about this, but we do want to think a little bit about how difficult it is. And so the general trade-off we think about is, how hard is it to infer what the errors are given the information versus how well does it perform
47:20
once we have used that information. So optimal decoding will find the recovery that's most likely to succeed given the syndrome. And for quantum codes, that's different than finding the error most likely to have occurred. For classical codes, it's not. This is this difference in degenerate codes. I mean, if you go to see a doctor, do you want to prescribe you the recovery that's most likely to succeed
47:41
or to tell you this is the most likely thing that you've got? You're really more interested in the former than the latter. And so that's why the optimal, it's important to think about the difference between those two. And that said, though, this most likely error decoder works pretty well in practice.
48:00
And so a lot of folks look at this as a decoder. It's still difficult. It's NP-hard in general, provably. Even though it's not optimal. And for CSS codes, you can express this as what's called an integer program. So you can throw it into your favorite numerical calculator and solve it to figure it out.
48:22
And for CSS codes, in fact, you can think of all CSS codes as a topological code in some geometry. And so you could come up with some crazy statistical mechanics model for which there's an order-disorder phase transition that maps to that threshold.
48:40
And for the special case of surface codes, that procedure becomes what's called minimum weight perfect matching, where you have all these syndrome bits and you try to pair together the syndrome bits and just pair-wise. You don't have to think about higher-order correlations. That algorithm generally runs in time D to the 7.5, where D is the distance
49:00
of the code. So a computer scientist will tell you this is only polynomial, but a programmer will tell you, oh my gosh, it's a lot. Recently, though, Austin Fowler and collaborators have tailored the algorithm specifically for the surface code and showed that you can actually parallelize this down to constant complexity.
49:20
So that's pretty exciting, that you can't go any better than that. And so this assumption that we made before of instantaneous classical computing is plausible if you use a decoder like this. It's not optimal, but it's pretty good and it's very fast. There's sort of an intermediate amount for concatenated codes.
49:42
Instead of trying to decode the concatenated code all at once, you can do it level by level. So at each level of the code, you decode it and hope that that does something, you know, it does well overall. So that's called level decoding. Or you can go and send some information back and forth between the levels through a kind of belief propagation network
50:01
or a renormalization group approach, where you make guesses for what the recovery is at a fine scale and pass messages back and forth between the levels of concatenation to iterate and can finally converge on a solution. And that tends to be fast also. It's not constant, but it's logarithm in the distance as opposed to some polynomial in the distance. So I'd say if you,
50:21
you know, in practice, something like, you know, one of these constant or log depth decoders is the one that you want to use. These polynomial time or NP-hard decoders might be good for assessing the best performance you could get out of these codes. So not worrying about the decoding complexity, just asking, you know, what to hope for out of these codes. They're useful for that, but not for anything
50:41
in practice. OK, so now we got to get the encoded gates. How do we, we've done fault-tolerant quantum error correction. I've told you all the pieces for that. Now how do I process it in encoded form? Again, here there are two general strategies for this. So one is to use transversal operations and the other is to use code deformation.
51:01
So in transversal operations, the idea is that you, each one of your codewords is stored in some block. So I've drawn it as like a plane here. And any time you want to do an encoded computation, like say a controlled knot, you do it transversely between let's say nearest neighbor planes. And so you do the same operation on every, between every pair of qubits in neighboring planes.
51:21
Now if you don't have a kind of pancake quantum computer like this, then you're going to have to move, add a bunch of additional movement things to make them nearest neighbor kind of operations to do pairwise. And that itself will add difficulties and complexities. So this is a good approach 3D quantum computer. For a 2D quantum computer, it presents some challenges.
51:42
A 2D quantum computer, however, can do code deformation. So you can take the lattice and deform the lattice and make it go through a bunch of gyrations and come back to itself. And if you do it in the right way, you can actually have encoded, you can have that information transform and you can do an encoded gate that way. There's this, the so-called
52:00
Teraya-Viro codes that can in fact do universal quantum computation just by deformation, by code deformations. Unfortunately, these are not stabilizer codes though, and it's not even known how to efficiently extract the syndrome from these things there. But they're kind of neat examples of how code deformation can give you very powerful results.
52:23
So how do transversal gates work? Well, you sort of got a hint of it a little bit in the extraction protocols. I'll distinguish between what I'll call transversal gates, which are where the gates act independently on each physical qubit in the code block, and strictly transversal where it's called. So a transversal operation might do like a C0 between the first
52:41
matching set of qubits and a C phase on the next ones and a controlled Y on the next one, whatever. Each one could be different, but independent of the other ones. Whereas the strictly transversal gate will be exactly the same between every pair of matched qubits. And we know that for any stabilizer code, we can do X, Z, and C0 transversely,
53:02
and even a destructive measurement transversely. So by destructive, I mean when you measure the bits, the bits are gone. There's no, it's not like you've projected the code word into an eigenstate of logical X or logical Z, but the bits are just, you're outside of the code space. So we can do that transversely.
53:21
We can actually, for CSS codes, do a lot of things strictly transversely. So we can do X or Z strictly transversely, say for odd length CSS codes, and even some even length ones. And when we have X and Z strictly transversal, we can do the Hadamard for strong CSS. So these are codes for which the H1 and H2 in Todd's talk would be the exact same matrix,
53:42
like the steam code, for example. You get this S or phase gate transversal for what are called doubly even CSS codes. and codes of a certain length, the length has to be 2L plus 1 mod 4. And if you do that, then if you use controlled I of the 2L plus 1 gates,
54:02
it'll give you the S gate transversely. I'm sorry, that's not supposed to be controlled. It's supposed to be Z of the, oh yeah, controlled I, I'm sorry. So controlled I is a single cubic gate. So like S is, for example, controlled I.
54:20
So doubly even, it basically is just saying that every, the weight of every generator of your stabilizer is a multiple of eight. It's a fancy way of saying that. Multiple of four, I'm sorry, and T is if it's a multiple of eight. It's quadruply even. So there's ways to get, you know, encoded gates to be strictly transversal, but you can't get them all transversal.
54:41
This is the so-called Easton-Nill theorem. It was proved earlier for stabilizer codes, but the Easton-Nill theorem works for all codes. However, there is a kind of a neat workaround with the three-dimensional color codes. You can ask me about this later, but there's a way to make it so that the only non-transversal operation you have is quantum error correction. And since you have to do that anyway,
55:01
and that's local quantum processing, maybe that's not such a big deal. So if you had a three-dimensional computer, you could get away with transversal operations everywhere except for quantum error correction. Once you have encoded magic states, then the S, T, and H gates
55:21
become transversal. So if you had a, if you just had as a source, these pi over two, pi over four plus states, the circuits I showed earlier, they all involve operations that I said were transversal. So that means that there's a transversal way to get these gates for any code. If you're stuck over here in this land without having these nice things, you can still get everything transversal
55:41
modulo not knowing how you prepared this pi over two, pi over four plus state. And so we need to have some way to prepare these magic states. We can't do it transversely because we can't get everything transversal, but we need to get high fidelity copies of these prepared by some mechanism. And in fact, you can even get these so-called
56:02
non-destructive measurements by using magic states as well. You don't need to have them, but they're handy to have. Code deformation, I'm actually not going to say a whole lot about code deformation because Robert's going to be talking about that. But the basic idea of this
56:20
is that you have a surface code, and one of those X or Z checks we remove from the code, and that creates a logical qubit. And then we can move these kind of holes around one another to affect a computation. This is like a space-time picture of the holes braiding around one another. And as they braid around one another,
56:41
you can get logic to happen. And it's very similar to, I'd say, cluster state quantum computation where you're driving things around by just measurements. And you're going to hear more about this from Robert. So magic, how do I get an encoded magic state? So I'm supposed to,
57:01
where does this thing come from in the first place? Well, there's two techniques we can use. We can inject it by teleportation or by code deformation. So in teleportation, what we do is we assume that we've got some way to make an encoded zero. Like, for example, we threw quantum error correction or threw these distillation protocols
57:20
I talked about earlier. We make a bell pair, we un-encode half of it and teleport the magic state in, and we get the encoded magic state that way. The problem with that is that when we've decoded bell pair, it's very exposed in that region. And so we get concerned about noise there.
57:41
For surface codes, another way we could do it is we could just grow it. So we could take our magic state and then just start growing a code around it, like a spider weaving a web around and around and around. So then it becomes better and better protected. But at the early stages, it's not very well protected. And depending how slowly the spider goes around, it's more exposed to noise in the early stages of growth.
58:01
But either way, these will give you states that are magic states in the code, but they might not have perfect fidelity because this injection process itself is not perfect. So we want to distill them in encoded form. Suppose we have many copies of the magic state,
58:22
but they're not perfect and we want to get higher quality versions of these. Well, since they're in encoded form, we can assume that the circuit we use to distill these is all perfect because it's encoded, so it's arbitrarily reliable. And to distill these pi over four states, it turns out we can run the coherent Steen encoding circuit in reverse.
58:41
And you send, I'm sorry, this is the Reed-Muller circuit, I should say. The Reed-Muller circuit in reverse, and you get 15 copies in and one copy comes out. And to get the pi over two, you can use seven copies in and get one copy out using the Steen encoder run in reverse. So I call this unencoding to distinguish it from decoding.
59:02
So there are thresholds for this, and it turns out that the thresholds are much higher than the thresholds for all the other operations in fault-tolerant quantum computing. So for the pi over four state, you can show that it's like 14.6%, you can reach up to 50% for the pi over two states. But there's a lot of repetition involved here,
59:20
just like there is for ancilla distillation. Reducing this overhead is an area of active research. It's the kind of thing that I think is being studied in Mark Heiligman's QCS program at IARPA. It's an exciting program that looks at the kinds of ways to reduce the overhead in fault-tolerant quantum computing. So let me finish here
59:40
with just a couple of words about the accuracy threshold. So as I mentioned, that's a tutorial unto itself to talk about how one estimates the threshold, either using Monte Carlo numerical techniques or using analysis techniques with exotic terms like extended rectangles, malignant pair counting, self-avoiding walks.
01:00:00
There really are tutorials unto themselves. The values that you see in the literature, they range from up to about 3% to like 10 to the minus 6, depending on the noise models that you look at. Where it'll end up, I don't know. And what's most realistic, I don't know. It's an active area. Upper bounds are particularly hard to come by.
01:00:22
The best upper bound we know is 29.3%. So you're never going to get a threshold higher than that. But that's not particularly informative, I would say. But it's something you can prove. So it's difficult to upper bound it. And the lower bounding requires specialized techniques.
01:00:42
So we're getting more into research-level stuff. What are all these thresholds? And maybe you'll hear more about this in some of these later talks. We're interested in getting the highest thresholds we can with the lowest amount of resources. That's kind of the name of the game in fault-taught quantum computing. So to summarize, I've told you about the four components
01:01:02
of a fault-taught quantum computing protocol. I've given you a high-level view of what all these things are about. And I've explained how you then use those four components to simulate an ideal circuit arbitrarily well. So when you put all these techniques together, it does allow you to do quantum computing, even in the presence of faults, to both the data and the processing.
01:01:22
You can simulate an ideal circuit arbitrarily well. And the amount of overhead that you incur is only polylogarithmic in the size of the original circuit. With that, I thank you for your attention. Thanks. Other questions? Pardon me, questions?
01:01:55
Sorry, did you hear that, or should I repeat? So the question was the 68% number that I quoted for the overhead for the Ancilla pipeline.
01:02:03
The question was, what algorithm was that for? That was, I actually forget the specific algorithm. It was more of an architecture, generally. It's true that it does depend on what the algorithm is to get the specifics. That paper was mostly focused on architectures.
01:02:22
I don't know, it would be a bit of conjecture. I don't remember exactly. Another question? Yeah, Todd?
01:02:44
So the question was, do I believe that this overhead for Ancilla distillation to be generic? Yes, I believe that it will take quite a bit. For any algorithm, I think it will take a substantial fraction of the resources. Whether or not it's always 68% or not, even though I don't believe that. I believe it will be substantial.
01:03:00
Yeah, I do. Okay, should we thank Todd and Andrew again? We have a bit of a break now, and then at 10.50, we'll continue. Okay, how about 11?