Gyakorlat – Erőforrások becslése valós problémára
A Shor faktoring algoritmusa az egyik legismertebb kvantum-algoritmus. Exponenciális gyorsítást kínál bármely ismert klasszikus faktoring-algoritmussal szemben.
A klasszikus titkosítás fizikai vagy matematikai eszközöket, például számítási nehézségeket használ egy feladat végrehajtásához. A népszerű titkosítási protokoll a Rivest-Shamir-Adleman (RSA) séma, amely azon a feltételezésen alapul, hogy a klasszikus számítógéppel nehéz lehet prímszámokat faktorálni.
A Shor algoritmusa azt jelenti, hogy a kellően nagy kvantumszámítógépek megszakíthatják a nyilvános kulcsú titkosítást. A Shor algoritmusához szükséges erőforrások becslése fontos az ilyen típusú titkosítási sémák sebezhetőségének felméréséhez.
A következő gyakorlatban kiszámítja a 2048 bites egész szám faktorálásának erőforrás-becsléseit. Ebben az alkalmazásban a fizikai erőforrás-becsléseket közvetlenül előre kiszámított logikai erőforrás-becslésekből fogja kiszámítani. A megengedett hibakerethez a $\epsilon = 1/3$ függvényt kell használnia.
A Shor algoritmusának írása
A Visual Studio Code-ban válassza a Parancspaletta megtekintése > lehetőséget, majd a Létrehozás: Új Jupyter-jegyzetfüzet lehetőséget.
Mentse a jegyzetfüzetet ShorRE.ipynb néven.
Az első cellába importálja a
qsharp
csomagot:import qsharp
A névtér használatával definiálhatja a
Microsoft.Quantum.ResourceEstimation
Shor egész számra optimalizált algoritmusának gyorsítótárazott, optimalizált verzióját. Adjon hozzá egy új cellát, és másolja és illessze be a következő kódot:%%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 Shors 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 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; }
A Shor algoritmusának becslése
Most az alapértelmezett feltételezések alapján becsülje meg a RunProgram
művelet fizikai erőforrásait. Adjon hozzá egy új cellát, és másolja és illessze be a következő kódot:
result = qsharp.estimate("RunProgram()")
result
A qsharp.estimate
függvény létrehoz egy eredményobjektumot, amellyel megjelenítheti a teljes fizikai erőforrásszámot tartalmazó táblázatot. A költségadatokat a csoportok összecsukásával vizsgálhatja meg, amelyek további információkkal rendelkeznek.
Csukja össze például a logikai qubitparaméterek csoportját, így láthatja, hogy a kód távolsága 21, a fizikai qubitek száma pedig 882.
Logikai qubitparaméter | Érték |
---|---|
QEC-séma | surface_code |
Kód távolsága | 21 |
Fizikai qubitek | 882 |
Logikai ciklus ideje | 8 milisecs |
Logikai qubit hibaaránya | 3.00E-13 |
Keresztezés előtagja | 0.03 |
Hibajavítási küszöbérték | 0,01 |
Logikai ciklusidő képlete | (4 * twoQubitGateTime + 2 * oneQubitMeasurementTime ) * codeDistance |
Fizikai qubitek képlete | 2 * codeDistance * codeDistance |
Tipp.
A kimeneti tábla kompaktabb verziójához használhatja result.summary
a következőt: .
Térdiagram
Az algoritmushoz és a T-gyárakhoz használt fizikai qubitek eloszlása olyan tényező, amely befolyásolhatja az algoritmus kialakítását. A csomag segítségével vizualizálhatja ezt a qsharp-widgets
disztribúciót, hogy jobban megértse az algoritmus becsült helyigényét.
from qsharp_widgets import SpaceChart
SpaceChart(result)
Ebben a példában az algoritmus futtatásához szükséges fizikai qubitek száma 829766, amelyek közül 196686 algoritmus qubitek, amelyek közül 633080 pedig T-gyári qubit.
A különböző qubit-technológiák erőforrás-becsléseinek összehasonlítása
Az Azure Quantum Resource Estimator lehetővé teszi a célparaméterek több konfigurációjának futtatását és az eredmények összehasonlítását. Ez akkor hasznos, ha össze szeretné hasonlítani a különböző qubitmodellek, QEC-sémák vagy hibakeretek költségeit.
A becslési paraméterek listáját az EstimatorParams
objektum használatával is létrehozhatja.
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)
Qubit-modell | Logikai qubitek | Logikai mélység | T állapotok | Kód távolsága | T gyárak | T gyári tört | Fizikai qubitek | rQOPS | Fizikai futtatókörnyezet |
---|---|---|---|---|---|---|---|---|---|
Kapualapú μs, 10⁻³ | 223 3,64M | 4,70 M | 17 | 13 | 40.54 % | 216,77k | 21,86k | 10 óra | |
Kapualapú μs, 10⁻⁴ | 223 | 3,64 M | 4,70 M | 9 | 14 | 43.17 % | 63,57k | 41,30k | 5 óra |
Kapualapú ns, 10⁻³ | 223 3,64M | 4,70 M | 17 | 16 | 69.08 % | 416,89k | 32,79 M | 25 másodperc | |
Kapualapú ns, 10⁻⁴ | 223 3,64M | 4,70 M | 9 | 14 | 43.17 % | 63,57k | 61,94 M | 13 másodperc | |
Majorana ns, 10⁻⁴ | 223 3,64M | 4,70 M | 9 | 19 | 82.75 % | 501,48k | 82,59 M | 10 másodperc | |
Majorana ns, 10⁻⁶ | 223 3,64M | 4,70 M | 5 | 13 | 31.47 % | 42,96k | 148,67 M | 5 másodperc |
Erőforrás-becslések kinyerve a logikai erőforrások számából
Ha már ismer néhány becslést egy művelethez, az Erőforrás-becslés lehetővé teszi az ismert becslések beépítése a teljes programköltségbe a végrehajtási idő csökkentése érdekében. Az LogicalCounts
osztály használatával kinyerheti a logikai erőforrás-becsléseket az előre kiszámított erőforrás-becslési értékekből.
Új cella hozzáadásához válassza a Kód lehetőséget, majd adja meg és futtassa a következő kódot:
logical_counts = LogicalCounts({
'numQubits': 12581,
'tCount': 12,
'rotationCount': 12,
'rotationDepth': 12,
'cczCount': 3731607428,
'measurementCount': 1078154040})
logical_counts.estimate(params).summary_data_frame(labels=labels)
Qubit-modell | Logikai qubitek | Logikai mélység | T állapotok | Kód távolsága | T gyárak | T gyári tört | Fizikai qubitek | Fizikai futtatókörnyezet |
---|---|---|---|---|---|---|---|---|
Kapualapú μs, 10⁻³ | 25481 | 1,2e+10 | 1,5e+10 | 27 | 13 | 0,6% | 37,38 M | 6 év |
Kapualapú μs, 10⁻⁴ | 25481 | 1,2e+10 | 1,5e+10 | 13 | 14 | 0,8% | 8,68 M | 3 év |
Kapualapú ns, 10⁻³ | 25481 | 1,2e+10 | 1,5e+10 | 27 | 15 | 1,3% | 37,65 M | 2 nap |
Kapualapú ns, 10⁻⁴ | 25481 | 1,2e+10 | 1,5e+10 | 13 | 18 | 1,2% | 8,72 M | 18 óra |
Majorana ns, 10⁻⁴ | 25481 | 1,2e+10 | 1,5e+10 | 15 | 15 | 1,3% | 26,11 M | 15 óra |
Majorana ns, 10⁻⁶ | 25481 | 1,2e+10 | 1,5e+10 | 7 | 13 | 0.5% | 6,25 M | 7 óra |
Összegzés
A legrosszabb forgatókönyvben egy kapualapú μs qubiteket használó kvantumszámítógépnek (a nanoszekundumos rendszerben működő qubiteknek, például a szupravezető qubiteknek) és a felületi QEC-kódnak hat év és 37,38 millió qubit kell ahhoz, hogy egy 2048 bites egész számot a Shor algoritmusával faktoráljon.
Ha más qubit technológiát használ – például kapualapú ns ion qubiteket –, és ugyanazt a felületi kódot használja, a qubitek száma nem változik sokat, de a futtatókörnyezet a legrosszabb esetben két nap, optimista esetben pedig 18 óra lesz. Ha megváltoztatja a qubit technológiát és a QEC-kódot – például Majorana-alapú qubitek használatával –, a 2048 bites egész szám Shor-algoritmussal történő faktorálásával órákon belül elvégezhető 6,25 millió qubitből álló tömb a legjobb esetben.
A kísérletből azt a következtetést vonhatja le, hogy a Majorana qubitek és a Floquet QEC-kód használata a legjobb választás a Shor algoritmusának végrehajtásához és a 2048 bites egész szám faktorálásához.