Esercizio - Stimare le risorse per un problema reale

Nell'unità precedente, hai imparato come usare lo strumento di stima delle risorse di Microsoft Quantum e come esplorare l'output.

In questo modulo, si stimano le risorse necessarie per fattorizzare un intero di 2.048 bit con l'algoritmo di Shor. L'algoritmo di fattorizzazione di Shor è uno degli algoritmi quantistici più noti. Offre un accelerazione esponenziale rispetto a qualsiasi algoritmo di factoring classico noto.

La crittografia classica usa metodi fisici o matematici, ad esempio difficoltà di calcolo, per eseguire un'attività. Un protocollo crittografico popolare è lo schema Rivest-Shamir-Adleman (RSA), basato sul presupposto che sia difficile trovare il numero primo di un numero intero molto grande in un computer classico.

L'algoritmo di Shor implica che i computer quantistici sufficientemente grandi possono interrompere la crittografia a chiave pubblica. Per valutare la vulnerabilità della crittografia a chiave pubblica, è importante stimare le risorse necessarie per eseguire l'algoritmo di Shor.

Nell'esercizio seguente si calcolano le stime delle risorse per l'algoritmo di Shor per considerare un numero intero a 2.048 bit. Per questa applicazione, si calcolano le stime delle risorse fisiche direttamente dalle stime delle risorse logiche pre-calcolate. Per il budget degli errori, usare $\epsilon = 1/3$.

Scrivere l'algoritmo di Shor

Per creare l'algoritmo di Shor in Q#, seguire questa procedura:

1. Apri Visual Studio Code (VS Code).

2. Aprire il menu Visualizza e quindi scegliere Riquadro comandi. Viene visualizzata una casella di input.

3. Nella casella di input immettere e scegliere Crea: Nuovo notebook di Jupyter.

4. Salvare il notebook come ShorRE.ipynb.

5. Nella prima cella importare il qsharp modulo e la EstimateDetails funzione dal qdk.widgets modulo:

   from qdk import qsharp
   from qdk.widgets import EstimateDetails
   

6. Aggiungere una nuova cella e quindi copiare il codice dell'algoritmo Shor seguente in tale cella:

   %%qsharp
   open Std.Arrays;
   open Std.Canon;
   open Std.Convert;
   open Std.Diagnostics;
   open Std.Intrinsic;
   open Std.Math;
   open Std.Measurement;
   open Std.Unstable.Arithmetic;
   open Std.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 Microsoft 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 Std.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;
   }
   

Stimare i requisiti delle risorse per l'algoritmo di Shor

È ora disponibile il codice per l'algoritmo di Shor. Anche se non si capisce esattamente come funziona il codice, è comunque possibile passare l'algoritmo allo strumento di stima delle risorse per misurare la disponibilità dell'esecuzione in un computer quantistico. Per iniziare, stimare le risorse necessarie per eseguire l'algoritmo con i valori predefiniti per i parametri dello strumento di stima delle risorse.

Aggiungere una nuova cella, quindi copiare ed eseguire il codice seguente in tale cella:

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

EstimateDetails(result)

La qsharp.estimate funzione crea un oggetto risultato che contiene informazioni dallo strumento di stima delle risorse. Si passa result alla funzione EstimateDetails, che visualizza un set di tabelle in menu a discesa che contengono l'output dello strumento di stima delle risorse.

Ad esempio, espandere il gruppo Parametri qubit logici per vedere che la distanza del codice è 21 e il numero di qubit fisici è 882.

Visualizzare il diagramma spaziale

Alcune considerazioni sulle risorse che potrebbero influire sulla progettazione dell'algoritmo includono la distribuzione di qubit fisici e il numero di qubit necessari per le factory T. Per visualizzare questa distribuzione e comprendere meglio i requisiti di spazio stimati dell'algoritmo, usare il widgets modulo .

Aggiungere una nuova cella, quindi copiare ed eseguire il codice seguente in tale cella:

from qdk.widgets import SpaceChart

SpaceChart(result)

Questa implementazione dell'algoritmo di Shor richiede un totale di 829.766 qubit fisici da eseguire, 196.686 di cui sono qubit di algoritmo e 633.080 di cui sono qubit di T factory.

Confrontare le stime delle risorse per tecnologie qubit diverse

Lo strumento di stima delle risorse consente di eseguire più configurazioni di parametri di destinazione e confrontare i risultati per ogni configurazione. Ciò è utile quando si vuole confrontare il costo di modelli qubit diversi, schemi QEC o budget di errore.

È anche possibile costruire un elenco di parametri di stima con l'oggetto EstimatorParams . Per confrontare le stime, aggiungere una nuova cella e quindi copiare ed eseguire il codice seguente in tale cella:

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)

Si ottiene una tabella come output che contiene le stime delle risorse per ogni modello:

Estrarre stime delle risorse dai conteggi delle risorse logiche

Quando si conoscono già alcune stime per un'operazione, lo strumento di stima delle risorse consente di incorporare le stime note nel costo complessivo del programma, riducendo così il tempo di esecuzione dello strumento di stima delle risorse. Usare la LogicalCounts classe per estrarre le stime logiche delle risorse dai valori di stima delle risorse precalcolati.

Aggiungere una nuova cella, quindi copiare ed eseguire il codice seguente in tale cella:

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

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

I valori nella nuova tabella di confronto sono interessati dai valori precalcolati passati a LogicalCounts.

Conclusione

Nello scenario peggiore, un computer quantistico che usa qubit basati su gate con tempi operativi nell'ordine dei microsecondi (come i qubit superconduttori) e un codice QEC di superficie richiederebbe sei anni e 37,38 milioni di qubit per fattorizzare un numero intero a 2.048 bit con l'algoritmo di Shor.

Se si utilizza lo stesso codice di superficie con una tecnologia di qubit diversa, ad esempio qubit ionici basati su gate ns, il numero di qubit non cambia significativamente, mentre il tempo di esecuzione diventa di due giorni nel peggior scenario e 18 ore nel miglior scenario. Se si modifica la tecnologia dei qubit e il codice QEC, ad esempio con qubit basati su Majorana, allora è possibile fattorizzare un numero intero a 2.048 bit con l'algoritmo di Shor in poche ore nel migliore dei casi, utilizzando una schiera di 6,25 milioni di qubit.

Dall'esperimento sembra che un computer quantistico con qubit Majorana e un codice QEC floquet sia la scelta migliore per eseguire l'algoritmo di Shor per considerare un intero a 2.048 bit.