Übung: Schätzen von Ressourcen für ein reales Problem

In der vorherigen Lektion haben Sie gelernt, wie Sie den Azure Quantum Resource Estimator verwenden und wie Sie seine Ausgabe untersuchen.

In dieser Einheit schätzen Sie die Ressourcen, die zum Faktorieren einer 2.048-Bit-Ganzzahl mit dem Shor-Algorithmus erforderlich sind. Der Faktoringalgorithmus von Shor ist einer der bekanntesten Quantenalgorithmen. Er bietet eine exponentiell höhere Geschwindigkeit gegenüber jedem bekannten klassischen Faktoringalgorithmus.

Klassische Kryptografie verwendet physikalische oder mathematische Methoden wie Rechenschwierigkeiten, um eine Aufgabe auszuführen. Ein beliebtes kryptografisches Protokoll ist das Rivest-Shamir-Adleman (RSA)-Schema, das auf der Annahme basiert, dass es schwierig ist, die Hauptzahlenfaktoren einer sehr großen ganzen Zahl auf einem klassischen Computer zu finden.

Der Algorithmus von Shor impliziert, dass ausreichend große Quantencomputer die Kryptografie mit öffentlichem Schlüssel unterbrechen können. Um die Sicherheitsanfälligkeit bei der Kryptografie mit öffentlichem Schlüssel zu bewerten, ist es wichtig, die zum Ausführen des Shor-Algorithmus erforderlichen Ressourcen zu schätzen.

In der folgenden Übung berechnen Sie die Ressourcenschätzungen für den Shor-Algorithmus, um eine 2.048-Bit-Ganzzahl zu faktorisieren. Für diese Anwendung berechnen Sie die physischen Ressourcenschätzungen direkt aus vorkompilierten logischen Ressourcenschätzungen. Für das Fehlerbudget verwenden Sie $\epsilon = 1/3$.

Schreiben Sie Shors Algorithmus

Führen Sie die folgenden Schritte aus, um den Shor-Algorithmus in Q# zu erstellen:

1. Öffnen Sie Visual Studio Code (VS Code).

2. Öffnen Sie das Menü "Ansicht ", und wählen Sie dann "Befehlspalette" aus. Ein Eingabefeld wird angezeigt.

3. Geben Sie im Eingabefeld "Erstellen: Neues Jupyter-Notizbuch" ein und wählen Sie die Option aus.

4. Speichern Sie das Notebook als ShorRE.ipynb.

5. Importieren Sie in der ersten Zelle das qsharp Paket und die EstimateDetails Funktion:

   import qsharp
   from qsharp_widgets import EstimateDetails
   

6. Fügen Sie eine neue Zelle hinzu, und kopieren Sie dann den folgenden Shor-Algorithmus-Code in diese Zelle.

   %%qsharp
   open Microsoft.Quantum.Arrays;
   open Microsoft.Quantum.Canon;
   open Microsoft.Quantum.Convert;
   open Microsoft.Quantum.Diagnostics;
   open Microsoft.Quantum.Intrinsic;
   open Microsoft.Quantum.Math;
   open Microsoft.Quantum.Measurement;
   open Microsoft.Quantum.Unstable.Arithmetic;
   open Microsoft.Quantum.ResourceEstimation;
   
   operation RunProgram() : Unit {
       let bitsize = 31;
   
       // When choosing parameters for `EstimateFrequency`, make sure that
       // generator and modules are not co-prime
       let _ = EstimateFrequency(11, 2^bitsize - 1, bitsize);
   }
   
   
   // In this sample we concentrate on costing the `EstimateFrequency`
   // operation, which is the core quantum operation in Shor's algorithm, and
   // we omit the classical pre- and post-processing.
   
   /// # Summary
   /// Estimates the frequency of a generator
   /// in the residue ring Z mod `modulus`.
   ///
   /// # Input
   /// ## generator
   /// The unsigned integer multiplicative order (period)
   /// of which is being estimated. Must be co-prime to `modulus`.
   /// ## modulus
   /// The modulus which defines the residue ring Z mod `modulus`
   /// in which the multiplicative order of `generator` is being estimated.
   /// ## bitsize
   /// Number of bits needed to represent the modulus.
   ///
   /// # Output
   /// The numerator k of dyadic fraction k/2^bitsPrecision
   /// approximating s/r.
   operation EstimateFrequency(
       generator : Int,
       modulus : Int,
       bitsize : Int
   )
   : Int {
       mutable frequencyEstimate = 0;
       let bitsPrecision =  2 * bitsize + 1;
   
       // Allocate qubits for the superposition of eigenstates of
       // the oracle that is used in period finding.
       use eigenstateRegister = Qubit[bitsize];
   
       // Initialize eigenstateRegister to 1, which is a superposition of
       // the eigenstates we are estimating the phases of.
       // We first interpret the register as encoding an unsigned integer
       // in little endian encoding.
       ApplyXorInPlace(1, eigenstateRegister);
       let oracle = ApplyOrderFindingOracle(generator, modulus, _, _);
   
       // Use phase estimation with a semiclassical Fourier transform to
       // estimate the frequency.
       use c = Qubit();
       for idx in bitsPrecision - 1..-1..0 {
           within {
               H(c);
           } apply {
               // `BeginEstimateCaching` and `EndEstimateCaching` are the operations
               // exposed by the Azure Quantum Resource Estimator. These will instruct
               // resource counting such that the if-block will be executed
               // only once, its resources will be cached, and appended in
               // every other iteration.
               if BeginEstimateCaching("ControlledOracle", SingleVariant()) {
                   Controlled oracle([c], (1 <<< idx, eigenstateRegister));
                   EndEstimateCaching();
               }
               R1Frac(frequencyEstimate, bitsPrecision - 1 - idx, c);
           }
           if MResetZ(c) == One {
               set frequencyEstimate += 1 <<< (bitsPrecision - 1 - idx);
           }
       }
   
       // Return all the qubits used for oracles eigenstate back to 0 state
       // using Microsoft.Quantum.Intrinsic.ResetAll.
       ResetAll(eigenstateRegister);
   
       return frequencyEstimate;
   }
   
   /// # Summary
   /// Interprets `target` as encoding unsigned little-endian integer k
   /// and performs transformation |k⟩ ↦ |gᵖ⋅k mod N ⟩ where
   /// p is `power`, g is `generator` and N is `modulus`.
   ///
   /// # Input
   /// ## generator
   /// The unsigned integer multiplicative order ( period )
   /// of which is being estimated. Must be co-prime to `modulus`.
   /// ## modulus
   /// The modulus which defines the residue ring Z mod `modulus`
   /// in which the multiplicative order of `generator` is being estimated.
   /// ## power
   /// Power of `generator` by which `target` is multiplied.
   /// ## target
   /// Register interpreted as LittleEndian which is multiplied by
   /// given power of the generator. The multiplication is performed modulo
   /// `modulus`.
   internal operation ApplyOrderFindingOracle(
       generator : Int, modulus : Int, power : Int, target : Qubit[]
   )
   : Unit
   is Adj + Ctl {
       // The oracle we use for order finding implements |x⟩ ↦ |x⋅a mod N⟩. We
       // also use `ExpModI` to compute a by which x must be multiplied. Also
       // note that we interpret target as unsigned integer in little-endian
       // encoding by using the `LittleEndian` type.
       ModularMultiplyByConstant(modulus,
                                   ExpModI(generator, power, modulus),
                                   target);
   }
   
   /// # Summary
   /// Performs modular in-place multiplication by a classical constant.
   ///
   /// # Description
   /// Given the classical constants `c` and `modulus`, and an input
   /// quantum register (as LittleEndian) |𝑦⟩, this operation
   /// computes `(c*x) % modulus` into |𝑦⟩.
   ///
   /// # Input
   /// ## modulus
   /// Modulus to use for modular multiplication
   /// ## c
   /// Constant by which to multiply |𝑦⟩
   /// ## y
   /// Quantum register of target
   internal operation ModularMultiplyByConstant(modulus : Int, c : Int, y : Qubit[])
   : Unit is Adj + Ctl {
       use qs = Qubit[Length(y)];
       for (idx, yq) in Enumerated(y) {
           let shiftedC = (c <<< idx) % modulus;
           Controlled ModularAddConstant([yq], (modulus, shiftedC, qs));
       }
       ApplyToEachCA(SWAP, Zipped(y, qs));
       let invC = InverseModI(c, modulus);
       for (idx, yq) in Enumerated(y) {
           let shiftedC = (invC <<< idx) % modulus;
           Controlled ModularAddConstant([yq], (modulus, modulus - shiftedC, qs));
       }
   }
   
   /// # Summary
   /// Performs modular in-place addition of a classical constant into a
   /// quantum register.
   ///
   /// # Description
   /// Given the classical constants `c` and `modulus`, and an input
   /// quantum register (as LittleEndian) |𝑦⟩, this operation
   /// computes `(x+c) % modulus` into |𝑦⟩.
   ///
   /// # Input
   /// ## modulus
   /// Modulus to use for modular addition
   /// ## c
   /// Constant to add to |𝑦⟩
   /// ## y
   /// Quantum register of target
   internal operation ModularAddConstant(modulus : Int, c : Int, y : Qubit[])
   : Unit is Adj + Ctl {
       body (...) {
           Controlled ModularAddConstant([], (modulus, c, y));
       }
       controlled (ctrls, ...) {
           // We apply a custom strategy to control this operation instead of
           // letting the compiler create the controlled variant for us in which
           // the `Controlled` functor would be distributed over each operation
           // in the body.
           //
           // Here we can use some scratch memory to save ensure that at most one
           // control qubit is used for costly operations such as `AddConstant`
           // and `CompareGreaterThenOrEqualConstant`.
           if Length(ctrls) >= 2 {
               use control = Qubit();
               within {
                   Controlled X(ctrls, control);
               } apply {
                   Controlled ModularAddConstant([control], (modulus, c, y));
               }
           } else {
               use carry = Qubit();
               Controlled AddConstant(ctrls, (c, y + [carry]));
               Controlled Adjoint AddConstant(ctrls, (modulus, y + [carry]));
               Controlled AddConstant([carry], (modulus, y));
               Controlled CompareGreaterThanOrEqualConstant(ctrls, (c, y, carry));
           }
       }
   }
   
   /// # Summary
   /// Performs in-place addition of a constant into a quantum register.
   ///
   /// # Description
   /// Given a non-empty quantum register |𝑦⟩ of length 𝑛+1 and a positive
   /// constant 𝑐 < 2ⁿ, computes |𝑦 + c⟩ into |𝑦⟩.
   ///
   /// # Input
   /// ## c
   /// Constant number to add to |𝑦⟩.
   /// ## y
   /// Quantum register of second summand and target; must not be empty.
   internal operation AddConstant(c : Int, y : Qubit[]) : Unit is Adj + Ctl {
       // We are using this version instead of the library version that is based
       // on Fourier angles to show an advantage of sparse simulation in this sample.
   
       let n = Length(y);
       Fact(n > 0, "Bit width must be at least 1");
   
       Fact(c >= 0, "constant must not be negative");
       Fact(c < 2 ^ n, $"constant must be smaller than {2L ^ n}");
   
       if c != 0 {
           // If c has j trailing zeroes than the j least significant bits
           // of y will not be affected by the addition and can therefore be
           // ignored by applying the addition only to the other qubits and
           // shifting c accordingly.
           let j = NTrailingZeroes(c);
           use x = Qubit[n - j];
           within {
               ApplyXorInPlace(c >>> j, x);
           } apply {
               IncByLE(x, y[j...]);
           }
       }
   }
   
   /// # Summary
   /// Performs greater-than-or-equals comparison to a constant.
   ///
   /// # Description
   /// Toggles output qubit `target` if and only if input register `x`
   /// is greater than or equal to `c`.
   ///
   /// # Input
   /// ## c
   /// Constant value for comparison.
   /// ## x
   /// Quantum register to compare against.
   /// ## target
   /// Target qubit for comparison result.
   ///
   /// # Reference
   /// This construction is described in [Lemma 3, arXiv:2201.10200]
   internal operation CompareGreaterThanOrEqualConstant(c : Int, x : Qubit[], target : Qubit)
   : Unit is Adj+Ctl {
       let bitWidth = Length(x);
   
       if c == 0 {
           X(target);
       } elif c >= 2 ^ bitWidth {
           // do nothing
       } elif c == 2 ^ (bitWidth - 1) {
           ApplyLowTCNOT(Tail(x), target);
       } else {
           // normalize constant
           let l = NTrailingZeroes(c);
   
           let cNormalized = c >>> l;
           let xNormalized = x[l...];
           let bitWidthNormalized = Length(xNormalized);
           let gates = Rest(IntAsBoolArray(cNormalized, bitWidthNormalized));
   
           use qs = Qubit[bitWidthNormalized - 1];
           let cs1 = [Head(xNormalized)] + Most(qs);
           let cs2 = Rest(xNormalized);
   
           within {
               for i in IndexRange(gates) {
                   (gates[i] ? ApplyAnd | ApplyOr)(cs1[i], cs2[i], qs[i]);
               }
           } apply {
               ApplyLowTCNOT(Tail(qs), target);
           }
       }
   }
   
   /// # Summary
   /// Internal operation used in the implementation of GreaterThanOrEqualConstant.
   internal operation ApplyOr(control1 : Qubit, control2 : Qubit, target : Qubit) : Unit is Adj {
       within {
           ApplyToEachA(X, [control1, control2]);
       } apply {
           ApplyAnd(control1, control2, target);
           X(target);
       }
   }
   
   internal operation ApplyAnd(control1 : Qubit, control2 : Qubit, target : Qubit)
   : Unit is Adj {
       body (...) {
           CCNOT(control1, control2, target);
       }
       adjoint (...) {
           H(target);
           if (M(target) == One) {
               X(target);
               CZ(control1, control2);
           }
       }
   }
   
   
   /// # Summary
   /// Returns the number of trailing zeroes of a number
   ///
   /// ## Example
   /// ```qsharp
   /// let zeroes = NTrailingZeroes(21); // = NTrailingZeroes(0b1101) = 0
   /// let zeroes = NTrailingZeroes(20); // = NTrailingZeroes(0b1100) = 2
   /// ```
   internal function NTrailingZeroes(number : Int) : Int {
       mutable nZeroes = 0;
       mutable copy = number;
       while (copy % 2 == 0) {
           set nZeroes += 1;
           set copy /= 2;
       }
       return nZeroes;
   }
   
   /// # Summary
   /// An implementation for `CNOT` that when controlled using a single control uses
   /// a helper qubit and uses `ApplyAnd` to reduce the T-count to 4 instead of 7.
   internal operation ApplyLowTCNOT(a : Qubit, b : Qubit) : Unit is Adj+Ctl {
       body (...) {
           CNOT(a, b);
       }
   
       adjoint self;
   
       controlled (ctls, ...) {
           // In this application this operation is used in a way that
           // it is controlled by at most one qubit.
           Fact(Length(ctls) <= 1, "At most one control line allowed");
   
           if IsEmpty(ctls) {
               CNOT(a, b);
           } else {
               use q = Qubit();
               within {
                   ApplyAnd(Head(ctls), a, q);
               } apply {
                   CNOT(q, b);
               }
           }
       }
   
       controlled adjoint self;
   }
   

Schätzen der Ressourcenanforderungen für den Shor-Algorithmus

Sie haben jetzt Code für den Shor-Algorithmus. Auch wenn Sie nicht genau verstehen, wie der Code funktioniert, können Sie den Algorithmus trotzdem an den Resource Estimator übergeben, um zu messen, wie lebensfähig es ist, auf einem Quantencomputer auszuführen. Schätzen Sie zunächst die zum Ausführen des Algorithmus erforderlichen Ressourcen mit den Standardwerten für die Parameter "Resource Estimator".

Fügen Sie eine neue Zelle hinzu, kopieren Sie den folgenden Code, und führen Sie den folgenden Code in dieser Zelle aus:

result = qsharp.estimate("RunProgram()")

EstimateDetails(result)

Die qsharp.estimate Funktion erstellt ein Ergebnisobjekt, das Informationen aus dem Ressourcen-Estimator enthält. Wir übergeben result an die EstimateDetails Funktion, die eine Reihe von Tabellen in Dropdowns anzeigt, die die Ausgabe aus dem Ressourcenstimator enthalten.

Erweitern Sie z. B. die Gruppe der logischen Qubit-Parameter , um festzustellen, dass der Codeabstand 21 ist und die Anzahl der physischen Qubits 882 ist.

Visualisieren des Raumdiagramms

Einige Ressourcenüberlegungen, die sich auf ihren Algorithmusentwurf auswirken könnten, sind die Verteilung physischer Qubits und die Anzahl der für T-Fabriken erforderlichen Qubits. Um diese Verteilung zu visualisieren und die geschätzten Platzanforderungen des Algorithmus besser zu verstehen, verwenden Sie das qsharp-widgets Paket.

Fügen Sie eine neue Zelle hinzu, kopieren Sie den folgenden Code, und führen Sie den folgenden Code in dieser Zelle aus:

from qsharp_widgets import SpaceChart

SpaceChart(result)

Diese Implementierung des Shor-Algorithmus erfordert insgesamt 829.766 physische Qubits, von denen 196.686 Algorithmus-Qubits und 633.080 T-Factory-Qubits sind.

Vergleichen von Ressourcenschätzungen für verschiedene Qubit-Technologien

Mit dem Ressourcen-Estimator können Sie mehrere Konfigurationen von Zielparametern ausführen und die Ergebnisse für jede Konfiguration vergleichen. Dies ist nützlich, wenn Sie die Kosten verschiedener Qubit-Modelle, QEC-Schemas oder Fehlerbudgets vergleichen möchten.

Sie können auch eine Liste der Schätzungsparameter mit dem EstimatorParams Objekt erstellen. Um Schätzungen zu vergleichen, fügen Sie eine neue Zelle hinzu, und kopieren Sie dann den folgenden Code in dieser Zelle, und führen Sie den folgenden Code aus:

from qsharp.estimator import EstimatorParams, QubitParams, QECScheme, LogicalCounts

labels = ["Gate-based µs, 10⁻³", "Gate-based µs, 10⁻⁴", "Gate-based ns, 10⁻³", "Gate-based ns, 10⁻⁴", "Majorana ns, 10⁻⁴", "Majorana ns, 10⁻⁶"]

params = EstimatorParams(6)
params.error_budget = 0.333
params.items[0].qubit_params.name = QubitParams.GATE_US_E3
params.items[1].qubit_params.name = QubitParams.GATE_US_E4
params.items[2].qubit_params.name = QubitParams.GATE_NS_E3
params.items[3].qubit_params.name = QubitParams.GATE_NS_E4
params.items[4].qubit_params.name = QubitParams.MAJ_NS_E4
params.items[4].qec_scheme.name = QECScheme.FLOQUET_CODE
params.items[5].qubit_params.name = QubitParams.MAJ_NS_E6
params.items[5].qec_scheme.name = QECScheme.FLOQUET_CODE

qsharp.estimate("RunProgram()", params=params).summary_data_frame(labels=labels)

Sie erhalten eine Tabelle als Ausgabe, die die Ressourcenschätzungen für jedes Modell enthält:

Extrahieren von Ressourcenschätzungen aus logischen Ressourcenzählungen

Wenn Sie bereits einige Schätzungen für einen Vorgang kennen, können Sie mit dem Ressourcen-Estimator die bekannten Schätzungen in die Gesamtkosten des Programms integrieren, wodurch die Laufzeit der Ressourcenschätzung reduziert wird. Verwenden Sie die LogicalCounts Klasse, um die logischen Ressourcenschätzungen aus vorberechnenden Ressourcenschätzwerten zu extrahieren.

Fügen Sie eine neue Zelle hinzu, kopieren Sie den folgenden Code, und führen Sie den folgenden Code in dieser Zelle aus:

logical_counts = LogicalCounts({
    'numQubits': 12581,
    'tCount': 12,
    'rotationCount': 12,
    'rotationDepth': 12,
    'cczCount': 3731607428,
    'measurementCount': 1078154040})

logical_counts.estimate(params).summary_data_frame(labels=labels)

Die Werte in der neuen Vergleichstabelle sind von den vorberechneten Werten betroffen, die Sie an LogicalCounts übergeben haben.

Zusammenfassung

Im schlimmsten Szenario benötigt ein Quantencomputer, der Gate-basierte μs-Qubits verwendet (Qubits mit Betriebszeiten im Mikrosekunden-Regime, z. B. superkonduktiver Qubits), und ein Oberflächen-QEC-Code benötigt sechs Jahre und 37,38 Millionen Qubits, um eine 2.048-Bit-Ganzzahl mit dem Shor-Algorithmus zu factorisieren.

Wenn Sie den gleichen Oberflächencode mit einer anderen Qubit-Technologie verwenden, z. B. Gate-basierte ns-Ionen-Qubits, dann ändert sich die Anzahl der Qubits nicht viel, aber die Laufzeit wird im schlimmsten Fall zwei Tage und 18 Stunden im optimistischen Fall. Wenn Sie die Qubit-Technologie und den QEC-Code ändern, beispielsweise auf Majorana-basierte Qubits, können Sie eine 2.048-Bit-Ganzzahl mit Shors Algorithmus im besten Fall innerhalb von Stunden mit einem Array von 6,25 Millionen Qubits faktorisieren.

Aus Ihrem Experiment scheint es, dass ein Quantencomputer mit Majorana-Qubits und einem Floquet QEC-Code die beste Wahl ist, um Shors Algorithmus auszuführen, um eine 2.048-Bit-Ganzzahl zu factorieren.