Quantum Algorithms in Quantum Computers

Gradu amaierako lana / Trabajo fin de grado Fisikako gradua / Grado en F´ısica Quantum algorithms in quantum computers Discussion and simulations of well-known quantum algorithms Egilea/ Autor/a: Xabier Fern´andez S´anchez Zuzendariak/ Directores/as: Dr. Mikel Sanz Ruiz cc by 2024 Xabier Fern´andez S´anchez Leioa, 2024ko ekainaren 29a / Leioa, 29 de junio de 2024 Contents 1 Introduction and objectives 2 2 Quantum computing 3 2.1 Review of quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Quantumcircuitmodel............................. 4 2.3 Elementary quantum gates . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Circuitcomplexity ............................... 6 2.5 Quantum Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5.1 Semi-classical version . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.6 Quantum Phase Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.6.1 Iterative Phase Estimation . . . . . . . . . . . . . . . . . . . . . . . 11 3 Grover’s algorithm 12 3.1 Searchingproblem ............................... 12 3.2 Quantumsearching............................... 12 3.3 Quantumcounting ............................... 15 4 Shor’s algorithm 17 4.1 Prime factorization problem . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 Fundamentals of modular arithmetics . . . . . . . . . . . . . . . . . . . . . 17 4.3 Shor’salgorithm................................. 18 4.3.1 Improvements.............................. 19 4.4 QuantumPeriodFinding............................ 20 4.5 Implementing modular gates . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.5.1 Addergate ............................... 23 4.5.2 Modular adder gate . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.5.3 Modular product gate . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.6 Finalimplementation.............................. 25 5 Algorithm simulations 27 5.1 Qiskit ...................................... 27 5.2 Grover’salgorithm ............................... 27 5.2.1 Quantumsearching........................... 28 5.2.2 Quantumcounting ........................... 30 5.3 Shor’salgorithm................................. 32 6 Conclusion 38 1 Chapter 1 Introduction and objectives The formulation and study of quantum mechanics have supposed a major revolution in the word of theoretical and experimental Physics. Indeed, the corresponding discoveries in this area have impacted both technology and the way we understand the world, shaping many modern technologies of everyday use nowadays. Over the second half of the 20th century, researchers independently began considering the idea of conceiving computers (therefore, machines that can run algorithms) under the principles of quantum mechanics: in the 80’s, Yuri Manin wrote about extended conventional computers with quantum mechanical phenomena like superposition and entanglement, and Richard Feynman considered the idea of simulating quantum mechanical systems under a computer which was itself built upon quantum mechanical principles [1]. The work of these and many more researchers began to gain fame in the 90’s, when theoretical results showed some quantum algorithms which efficiently solved problems without an efficient algorithm for a classical computer. Currently, quantum algorithms are implemented in the so-called NISQ/noisy intermediate-scale quantum computers, characterized by medium-sized quantum processes with remarkable noise problems. In this work, two of the most well-known quantum algorithms are discussed and simulated. An initial theoretical introduction is given, starting with some fundamentals of quantum mechanics which are used in quantum computing. Grover’s algorithm is then introduced, along with the related quantum counting algorithm. Shor’s algorithm is introduced afterwards, with a particular implementation that is discussed, implemented and simulated. Quantikz [2] L A T EX package is used for rendering all quantum circuits. The majority of implementations are programmed with Python and Qiskit. The programmed source code is available in the repository of the University of the Basque Country (ADDI). Simulations cover the results of thousands of circuit runs in order to estimate the probabilities of each possible measurement. Simulation results are discussed and compared with theoretical predictions. The study of such quantum algorithms showcases the unique properties that quantum computing has, compared to its classical counterpart. It is shown that entanglement plays a key role on the phase estimation procedure, a base component of both Shor’s and Grover’s algorithms. The nature of quantum computing is illustrated overall, consisting of cleverly creating superpositions and destructive interferences of quantum states in order to be able to obtain information when quantum system qubits are measured. 2 Chapter 2 Quantum computing 2.1 Review of quantum mechanics A quantum mechanical system is mathematically described by a Hilbert space Hwhere the system’s state is described using bras ⟨Ψ|and kets |Ψ⟩. The time evolution of the system is subject to a Hamiltonian represented by a Hermitian operator H, and it is described by the Schr¨odinger equation, H|Ψ⟩=iℏ∂|Ψ⟩ ∂t .(2.1) The system state can be expressed as a normalized linear combination of elements from a chosen basis {|ϕi⟩}: |Ψ⟩=X i ci|ϕi⟩,X i|ci|2= 1 .(2.2) According to Born’s rule, measurements with respect to that (and any other) basis essentially project the state over the i-th basis state with probability |ci|2, hence collapsing |Ψ⟩into a pure basis state. For instance, if the quantum state |Ψ⟩=1 2|ϕ1⟩+√2 2|ϕ2⟩+1 2|ϕ3⟩ is measured, it will collapse to |Ψ⟩=|ϕ1⟩with probability 1 22= 25%. The Schr¨odinger equation can be alternatively expressed to describe the time evolution of a quantum state with a unitary evolution operator, |Ψ(t)⟩=e−iH ℏt|Ψ⟩.(2.3) This alternative formulation illustrates the concept of applying unitary operators Uin order to interact with states and transform them. An operator Umay be expressed in matrix form Uij with respect to a certain basis {|ϕi⟩}, so that (Uij) = (⟨ϕi|U|ϕj⟩). For example, in a spin-1/2 particle system with basis states |↑⟩and |↓⟩(eigenstates of the Z-component of spin operator Sz), an operator acting the following way would have the following matricial expression, U|↑⟩ =|↓⟩, U |↓⟩ =|↑⟩ −→ U=0 1 1 0.(2.4) 3 2.2. QUANTUM CIRCUIT MODEL In fact, this is the expression of one of the Pauli matrices, a useful quantum gate introduced below. 2.2 Quantum circuit model Following the parallelism with classical computing, a two-dimensional quantum system with basis states |0⟩,|1⟩can be compared to a classical bit. Such quantum system is quite well known in quantum mechanics and particle physics, since it describes the state of a 1/2-spin particle such as quarks and leptons. This system describes the state of a qubit, with this basis known as the computational basis, but other bases may be considered for specific purposes. From now on, this will be considered as the default basis, and computational basis states will simply be referred to as basis states. A quantum system composed of several qubit states constitutes a multi-qubit system, whose basis states are defined and named as |0⟩⊗|1⟩=|01⟩,|1⟩⊗|1⟩=|11⟩for two-bit systems, |011⟩for three-bit systems and so on. An n-qubit state is therefore a superposition of 2nbasis elements. Quantum states of multi-qubit systems are product states if they can be expressed as a tensor product of individual states, and are entangled states otherwise. Entanglement is a key property in quantum mechanics, since measurements in one qubit may affect other qubits despite not measuring them at all. For instance, the two-qubit state 1 √2(|0⟩+i|1⟩)⊗|0⟩is a product state (measurements on one of the qubits does not affect the state of the other) while the state 1 √2(|00⟩+|11⟩) is an entangled state (measuring one of the qubits will also affect the state of the other qubit). A single qubit basis state can be used to encode a bit and, analogously, an n-qubit basis state can be used to encode an n-bit sequence. Such particular qubit groupings encoding bit sequences/bitstrings are known as quantum registers and are analogous to classical n-bit registers. From now on, the notation of |x⟩nwill correspond to the n-qubit basis state encoding an-bit integer xin binary. For example, the four-qubit state |1001⟩may be denoted as |9⟩4. Moreover, |x⟩(k)will be used to index a particular qubit of a multi-qubit register, where indexing begins from the least significant bit (the bit corresponding to the power 20in base-2 representation). In the previous example, |9⟩(0) would correspond to a qubit |1⟩and |9⟩(2) would correspond to a qubit |0⟩. Like with classical registers, a certain convention must be followed to index or to order qubits / their encoded bits in a register, usually known as the endianess. The usual convention implicitly followed in math and physics is big-endian ordering, characterized by the least significant bit as the last bit. For example, the integer 11 is expanded as 1·23+0·22+1·21+1·20, it is represented in big-endian ordering as 1011. The convention followed here is little-endian ordering, frequently used in Software Engineering, where the order is the opposite thus the least significant bit being the first. Under this ordering, 11 is represented as 1101. Under this model, n-qubit algorithms are constructed by applying unitary operators to one or several qubits, also known as quantum gates or simply gates in this context, along 4 2.3. ELEMENTARY QUANTUM GATES with potential qubit measurements into classical bits. Such algorithms are represented by diagrams such as the example showcased in Fig. 2.1. |0⟩A C |1⟩B Space Time Figure 2.1: Example of a two-qubit quantum circuit. The Agate acts on the first qubit, the Bgate acts on the second qubit, and the gate Cacts on both qubits. By encoding information in the basis states, gates acting on the state act “simultaneously” on all basis states present in the superposition: U(|ϕ1⟩+|ϕ2⟩+... +|ϕn⟩) = U|ϕ1⟩+U|ϕ2⟩+... +U|ϕn⟩.(2.5) This is the powerful property of quantum computing which may be harnessed to construct algorithms more efficient than their classical counterparts. Nevertheless, since measurements are the only way to retrieve any information from the quantum state, this property is severely limited in practice due to the state being collapsed to the measured basis state afterwards. The design of efficient quantum algorithms therefore consists of cleverly extracting information from the quantum system. The defining property for unitary gates is that U†=U−1, where the dagger operator is a conjugate transpose obtained by transposing Uand then applying complex conjugation to each entry of its matricial expression. This property of unitarity implies that all gates are invertible. Hence, unlike classical computing with conventional logical gates, quantum computing is reversible with the notorious exception of measurements. Nevertheless, in many quantum circuits measuring is done at the end as a final step for extracting information. 2.3 Elementary quantum gates The two-dimensional Pauli matrices, widely used in quantum mechanics, are well-known single-qubit gates. There are referred by various names in this model, such as X, Y, Z: X=0 1 1 0, Y =0−i i0, Z =1 0 0−1.(2.6) In particular, the Xgate is also called the NOT gate for it being identical to the classical NOT logic gate, since its action flips the qubit state: X|0⟩=|1⟩and X|1⟩=|0⟩ Another widely used quantum gate is the Hadamard gate, particularly useful for state initialization since it creates equiprobable superpositions from pure basis states: H=1 √21 1 1−1, H|0⟩=1 √2(|0⟩+|1⟩), H|1⟩=1 √2(|0⟩−|1⟩). (2.7) 5 2.4. CIRCUIT COMPLEXITY Phase gates introduce a complex phase eiϕ if the qubit is |1⟩and leave the qubit unchanged otherwise: R±j=1 0 0e±i2π 2j,Rj(α|0⟩+β|1⟩) = α|0⟩+βei2π 2j|1⟩, R−j(α|0⟩+β|1⟩) = α|0⟩+βe−i2π 2j|1⟩.(2.8) A particularly useful type of gates are controlled gates, constructed by generalizing existing gates so that they are controlled by an additional qubit. Such gates are represented as shown in Fig. 2.2 in circuits. . . . . . . |Φ⟩control |Ψ⟩nUtarget Figure 2.2: Graphical representation of a gate Uacting on the n-qubit register |Ψ⟩nand controlled by the qubit |Φ⟩. An n-qubit gate Ucontrolled by an arbitrary qubit and applied to an arbitrary n-qubit register (the two may be entangled) has the following expression, CU (α|0⟩⊗|Φ⟩n+β|1⟩⊗|Ψ⟩n) = α|0⟩⊗|Φ⟩n+β|1⟩⊗U|Ψ⟩n.(2.9) It follows that this additional qubit, known as the control qubit, is essentially acting as a conditional Boolean value (true or false value) typically used on classical algorithms: if the control qubit is 0 (false), then the gate leaves the remaining qubits unchanged, and otherwise (1/true) it does act on them. The control qubit will be generally any superposition of |0⟩and |1⟩, in which case applying the controlled gate may introduce entanglement between the control qubit and the rest. Swap gates, which can swap the states of two qubits (and may be combined/generalized to swap more) may be constructed from other elementary gates. 2.4 Circuit complexity Similar to classical computing, the resource requirements of a quantum circuit are a crucial aspect to study. The relevant quantifiable resources in the context of a quantum circuit are memory, which is determined by the required qubit count, and time, related to the number of gates it is composed of. The depth of a circuit consists of the number of distinct timesteps at which gates are applied in a circuit. In several quantum circuits, gates may be applied in parallel during the same timestep, as can be seen in the quantum circuit illustrated in Fig. 2.3. |0⟩H U X |1⟩H Figure 2.3: Simple quantum circuit in which the initial Hadamard gates may be applied in parallel. 6 2.5. QUANTUM FOURIER TRANSFORM 2.5 Quantum Fourier Transform The Fourier Transform is a widely known and used subroutine in Physics and Engineering. The Discrete Fourier Transform performs the following transformation for a set of Ninput values {x1, ..., xN}: xj→ N−1 X k=0 xke−i2πjk N.(2.10) By conveniently combining Hadamard and controlled phase gates, a quantum algorithm analogous the Discrete Fourier Transform can be constructed as shown in Fig. 2.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . |ϕ⟩(n−1) HR2Rn−1Rn |ϕ⟩(n−2) HRn−2Rn−1 |ϕ⟩(1) HR2 |ϕ⟩(0) H QFT Figure 2.4: General n-qubit circuit for the Quantum Fourier Transform subroutine [3]. The circuit transforms an n-qubit basis state |x⟩nin the following equivalent forms: QFT |x⟩n=1 √2n 2n−1 X k=0 ei2πkx 2n|k⟩n =1 √2(|0⟩+ei2πx 2n|1⟩)⊗···⊗ 1 √2(|0⟩+ei2πx 21|1⟩). (2.11) Therefore, the application of circuit 2.4 is a transformation analogous to the classical discrete Fourier transform for a set of N= 2ninputs. A total of n(n−1)/2 gates are used for the n-qubit version, resulting in size and depth of O(n2). The most famous classical algorithm is the fast Fourier transform or FFT, which has complexity O(Nlog N) where Nis the input value count. Comparing both complexities yields O(n2) for the QFT and O(n2n) for the FFT. The FFT has exponential complexity compared with the polynomial complexity of QFT, hence showing the exponential speedup that the quantum version provides. Note, however, that from the QFT only a single value may be measured and the quantum state will have collapsed afterwards, while from any classical FT all transformed values are retrieved. 2.5.1 Semi-classical version Any algorithm composed of a QFT/inverse QFT immediately followed by a measurement, and optionally single-qubit gates before/after the (inverse) QFT, is subject to a major improvement in qubit requirement. In the QFT circuit illustrated in Fig. 2.4, the effect of the QFT acting on the first qubit 7 2.6. QUANTUM PHASE ESTIMATION |ϕ⟩(0) consists of the application of a single Hadamard gate. This (along other potential single-qubit gates before/after the QFT, plus a final measurement) means that the qubit is effectively independent from the rest and the gates and measurement acting on it could be performed without them. Applying the (inverse) QFT on the second qubit |ϕ⟩(1) involves applying a Hadamard gate and a phase gate controlled by the first qubit, but it can be shown that, if the first qubit is acted and measured beforehand, the controlled phase gate can be replaced by a regular phase gate applied conditionally by the first qubit measurement bit as shown in Fig. 2.5. |ϕ⟩(1) HR2 y(1) |ϕ⟩(0) H y(0) |ϕ⟩(0) H y(0) |ϕ⟩(1) HR2 y(1) y(0) Figure 2.5: Comparison of the 2-qubit QFT circuit (top) and its semi-classical version (bottom), reusing a single qubit. The R2gate is only applied if the measured bit y(0) is 1, denoted by dashed lines. The same thing follows for all nqubits, depending on previous qubit measurements. This can be exploited to simplify (inverse) QFT circuits by using a single qubit and effectively splitting the procedure into ncycles, known as the semi-classical (inverse) QFT and illustrated in Fig. 2.6. . . . . . . |ϕ⟩(0) H x(0) |ϕ⟩(1) HR2 x(1) |ϕ⟩(n−1) HRnR2 x(n−1) Cycle 1 Cycle 2 x(0) Cycle n x(0) x(n−2) . . . . . . |ϕ⟩(0) H x(0) |ϕ⟩(1) R−2H x(1) |ϕ⟩(n−1) R−nR−2H x(n−1) Cycle 1 x(0) Cycle 2 x(0) Cycle n x(n−2) Figure 2.6: General n-qubits for the semi-classical versions of the QFT (top) and inverse QFT (bottom) respectively. 2.6 Quantum Phase Estimation Any given unitary gate Uhas its corresponding eigenstates {|ej⟩}and eigenvalues {ei2πϕj} where ϕj∈[0,1), so that U|ej⟩=ei2πϕj|ej⟩. If we wish to obtain the phase ϕjcorresponding to a certain eigenstate |ej⟩, nothing can be obtained by simply applying the 8 3.3. QUANTUM COUNTING . . . . . . . . . . . . . . . . . . . . . . . . . . . |0⟩(n−1) H O H J H x(n−1) |0⟩(n−2) H H H x(n−2) |0⟩(1) H H H x(1) |0⟩(0) H H H x(0) Grover iteration G(repeated Rtimes) Diffusion operator Q Figure 3.2: General n-qubit circuit for Grover’s algorihm with Riterations. An n-bit integer xis measured corresponding to basis state |x⟩n. Since the oracle query count is given by R, from Eq. 3.9 it follows that the circuit has an upper bound of O√Non the query complexity, hence quadratically improving the already discussed O(N) bound of classical searching. 3.3 Quantum counting In a searching problem the amount of searchable target items Mis usually unknown. The separate problem of estimating Mis known as the counting problem. Fortunately, with the gates described for the searching algorithm, a straightforward procedure for such problem can be designed. In the subspace Sand its corresponding basis of {|α⟩,|β⟩}, the Grover iteration G happens to have the following two eigenvector-eigenvalue pairs: G1 √2(−i|α⟩+|β⟩)=e−i2θ1 √2(−i|α⟩+|β⟩), G1 √2(i|α⟩+|β⟩)=ei2θ1 √2(i|α⟩+|β⟩). (3.10) The phases are conveniently 2θ/2πand −2θ/2π, where a negative phase −2θis equivalent to 2π−2θto be made positive. Since |Ψ0⟩is an equiprobable superposition of |α⟩ and |β⟩, by Eqs. 3.10, it is also an equiprobable superposition of both Geigenstates. Therefore, a phase estimation procedure with Gas the unitary and |Ψ0⟩as the initial state allows the extraction of either phases. The corresponding quantum circuits are given in Figs. 3.3 and 3.4 for original and iterative phase estimation respectively. 15 3.3. QUANTUM COUNTING . . . . . . . . . . . . . . . |0⟩(m−1) H QFT−1 t(m−1) . . . |0⟩(1) H t(1) |0⟩(0) H t(0) |0⟩(n−1) H G20G20G2m−1 . . . |0⟩(0) H Figure 3.3: Quantum counting problem circuit based on the original Quantum Phase Estimation procedure. The circuit has total of m+nqubits, organized as two m-qubit and n-qubit registers. |0⟩H H t(0) |0⟩HR−2H t(1) ... |0⟩nH⊗nG2m−1G2m−2... Cycle 1 Cycle 2 t(0) . . .... |0⟩HR−mR−2H t(m−1) ... G20 Cycle m t(0) t(m−2) Figure 3.4: Quantum counting problem circuit based on the iterative Quantum Phase Estimation procedure. The circuit has total of n+ 1 qubits, organized as a n-qubit register and a single qubit. In the classical post-processing after the phase estimation procedure, an optimal measurement will yield an m-bit integer t= 2m2θ/2πor t= 2m(2π−2θ)/2π. From expression 3.6 Mmay be obtained, since θcan be computed from the measured value: t1≈2mθ π= 2mϕ1 π, ϕ1=θ , t2≈2m1−θ π= 2mϕ2 π, ϕ2=π−θ . (3.11) These angles are hence related by ϕ2=π−ϕ1; by trigonometric identities it follows that sin ϕ1= sin ϕ2, so both measurements tjresult in the same estimation of M: M≈Nsin2πtj 2m.(3.12) 16 Chapter 4 Shor’s algorithm 4.1 Prime factorization problem The prime factorization problem is a widely known problem in Computer Science. The idea is straightforward: given an integer Nknown to be a product of two unknown prime integers pand q, the task is to determine pand q, hence to factor N. The opposite task (given pand q, multiply them to obtain N) is trivial and can be done efficiently in virtually any classical computer as it consists of a mere integer multiplication. This shows that, given potential guesses p′and q′, they can be easily checked. Several algorithms exist for solving such a problem, but none of the classical ones is efficient. One of these algorithms, Shor’s quantum algorithm, is discussed in this section. 4.2 Fundamentals of modular arithmetics The procedure for Shor’s algorithm is rooted in number theory and modular arithmetics. Under modular arithmetics, operations with integer values wrap around the modulus. The most familiar example are time units, where hours in a 12−hour clock operate under mod-12, and minutes and seconds under mod-60. Equivalence relations in modular arithmetics are congruent relations denoted using mod. For example: under mod-12 arithmetics, the addition operation 5 + 8 equals 1. The congruence relation behind this operation is 13 ≡1 (mod 12). More generally, the congruence relation a≡b(mod n) is equivalent to a=b+xn for some particular integer x, which can be seen as that integer values aand bdiffer by a multiple of the modulus n. Given any natural number k, all natural numbers smaller than kand coprime with k (sharing no prime factors with k) along with 1 form a group under mod-kmultiplication which will be denoted by Gk. For instance, for k= 15 the corresponding group is G15 ≡ {1,2,4,7,8,11,13,14}. Since Gkis a finite group, it follows that every element ahas its corresponding order r, which is the smallest positive integer satisfying the following property: 17 4.3. SHOR’S ALGORITHM rtimes z }| { a·a·. . . ·a=ar≡1 (mod k) (4.1) This property illustrates the periodicity of mod-kproducts over the group elements: repeated products by a particular group element awill eventually loop and result in element 1, and applying further products by awill repeat the loop again. In fact, the order rof ais precisely the amount of products needed before the successive product applications loop back to the starting value. An example of sequential mod-15 multiplications is illustrated in Fig. 4.1. 4·7 (mod 15) = 13 13 ·7 (mod 15) = 1 1·7 (mod 15) = 7 7·7 (mod 15) = 4 4 13 1 7 k= 15, a =7:r= 4 Figure 4.1: Loop resulting by repeated products by 7 under mod-15 arithmetics. The corresponding order is r= 4. The size of the group Gkwill always be smaller than k. This follows since the largest group comprises k−1 elements, which is the case for a prime kwhere every integer between 1 and k−1 is coprime to k. For any non-prime k, the group size will be smaller, since at least one of those k−1 smaller integers will share some prime factor with k. From here, it also follows that r < k for any group element a, since the eventual loop reached by successive aproducts cannot be larger than the group itself before elements start to repeat. 4.3 Shor’s algorithm This background in modular arithmetics may be used to factor our input integer Nby taking the finite group GNcorresponding to mod-Narithmetics. By taking a group element aand supposing its corresponding order ris even, Eq. 4.1 may be factored as ar/2+ 1ar/2−1≡0 (mod N).(4.2) Such an expression is equivalent to stating that ar/2+ 1ar/2−1is a multiple of N, i.e. nis contained as a factor between both factored terms. The expression can be satisfied in possible manners: two trivial cases and a remaining nontrivial case. The two trivial cases are when the expression is individually satisfied by a single term: 18 4.3. SHOR’S ALGORITHM ar/2+ 1 ≡0 (mod N), ar/2−1≡0 (mod N).(4.3) In such cases, Nis contained as a factor exclusively on one of the two terms. The latter of such cases is equivalent to Eq. 4.1 with exponent r/2. However, this is not possible since ris by definition the smallest positive integer satisfying the equation. Nevertheless, the former trivial case may be satisfied: such a case gives no useful information about N or its prime factors. In the nontrivial case, N=pq is a factor of both terms combined but not individually of a single term. Therefore, pand qmust be factors of each term separately, so they can be extracted as the greatest common divisor of Nand each term: p= gcdar/2−1, N, q = gcdar/2+ 1, N.(4.4) The greatest common divisor of two integers can be efficiently computed using Euclid’s algorithm. Thus, given an element a∈GNwhose order ris even and assuming that the property given by Eq. 4.2 is not trivially satisfied, Ncan be successfully factored. This is the core idea behind Shor’s algorithm, whose procedure stems from: 1. Choose an integer a∈[2, N −1]. 2. Check whether a∈GN. If otherwise, aand Nshare a factor and thus pand qare straightforward to obtain (this, however, gets extremely unlikely the bigger Nis): p= gcd(a, N), q =N/p . (4.5) 3. Find the order rof a. 4. Verify that ris even and that Eq. 4.3 is not satisfied. If otherwise, repeat the procedure with a different integer a. 5. Extract pand qas in Eq. 4.4 and thus successfully factor N. All procedure steps happen to be clasically efficient, but for the step regarding computing the order r. Peter W. Shor [4] devised a quantum algorithm which efficiently finds orders: the Quantum Period Finding routine. Note that order and period will be used as sinonyms, both referring to the same property rof a given group element a. 4.3.1 Improvements So far the original Shor’s algorithm has been discussed, but minor improvements have been made over time. One relevant improvement [5] relaxes the requirement for even orders: if ahappens to be a square integer of the form a=b2, then expression 4.2 may be still valid1in terms of bdespite rbeing odd: (br+ 1) (br−1) ≡0 (mod N).(4.6) This alternative expression may be again satisfied by two trivial cases and a general nontrivial one, but the situation is not entirely the same as before. ris not the order of 1If a=b2,bis also a group element: b∈GN. 19 4.4. QUANTUM PERIOD FINDING bbut the order of a, since bwill have its own order which we shall name s. Note that s might be a factor of r, in which case there is no longer a forbidden trivial case, and both need to be taken into account. This idea may be generalized for elements of the form a=b2k, where bis the irreducible root of a. In Ref. [5] it is shown that factoring with binstead of ais the same at worst, or preferable at best. In other words, for some elements a, factoring may fail (a trivial case is satisfied) but factoring with their root bhappens to be successful and does not have that problem. This will later be shown with some explicit examples. 4.4 Quantum Period Finding A quantum algorithm for reasonably estimating the order of a given element acan be constructed using phase estimation, known as the Quantum Period Finding algorithm. The algorithm is designed by providing a q-qubit quantum gate Ua,N performing mod-N multiplication2by a value a, Ua,N |x⟩q=|(a·x) (mod N)⟩q.(4.7) Such a gate has reigenstate/eigenvalue pairs, indexed with s= 0, ..., r −1: |ψs⟩q=1 √r r−1 X k=0 e−i2πk s rak(mod N)q, Ua|ψs⟩q=ei2πs r|ψs⟩q.(4.8) A pure eigenstate cannot be prepared as an initial state, since rwould need to be known beforehand, but the following property of the sum of eigenstates can be exploited 1 √r r−1 X s=0 |ψs⟩n=|1⟩n.(4.9) Therefore, the pure basis state |0...01⟩≡|1⟩nis precisely the equiprobable superposition of all Ua,N eigenstates. By starting with such state as the initial state and performing the phase estimation procedure, a value of 2ms/r may be extracted. The corresponding circuits, with iterative and regular phase estimation, are represented in Figs. 4.2 and 4.3 respectively. |0⟩H H y(0) |0⟩HR−2H y(1) ... |1⟩qUa2m−1,N Ua2m−2,N ... Cycle 1 Cycle 2 y(0) . . .... |0⟩HR−mR−2H y(m−1) ... Ua20,N Cycle m y(0) y(m−2) Figure 4.2: Quantum Period Finding (QPF) circuit based on the iterative phase estimation procedure. The circuit has total of q+ 1 qubits, organized as a q-qubit register and a single qubit. 2Mod-Nmultiplication is not an invertible operation. For instance, every multiple of 15 (hence x= 0,15,30,45,60,75...) satisfies x≡0 (mod 15). However, an implementation of Ua,N is discussed in this work, showing that it can be constructed with the aid of ancillary/auxiliary qubits. 20 4.4. QUANTUM PERIOD FINDING . . . . . . . . . . . . . . . |0⟩(m−1) H QFT−1 y(m−1) . . . |0⟩(1) H y(1) |0⟩(0) H y(0) |1⟩(q−1) Ua20,N Ua21,N Ua2m−1,N . . . |1⟩(0) Figure 4.3: Quantum Period Finding (QPF) circuit based on the original phase estimation procedure. The circuit has total of m+qqubits, organized as two m-qubit and q-qubit registers. Nevertheless, extracting s/r still does not give away the period: sis an unknown value between 0, ..., r −1, and ris the desired value to compute, also unknown. Moreover, the measured value ymay not even be exactly 2ms/r, but the closest integer to it, provided an optimal measurement was performed. Thus, the measured value needs to be processed in order to reasonably extract r. Continued fraction expansions may be used for this purpose. Given the rational number y/2m, it can be expanded by its continued fraction expansion which is described by a finite set of coefficients {a1, a2, ..., av} y 2m=1 a1+1 a2+1 a3+... .(4.10) From now on, when discussing any post-processing of a Quantum Period Finding measurement, the equivalence between a fraction and its continued fraction expansion coefficients will be stated as the following relation y 2m≡ {a1, a2, ..., av}. The convergents of a continued fraction expansion are defined as truncations of the coefficient set: fractions corresponding to coefficients {a1},{a1, a2},{a1, a2, a3}and so on are convergents of y/2m. As an example, fraction 68/157 has expansion coefficients {2,3,4,5}, 68 157 =1 2 + 1 3+ 1 4+ 1 5 ≡ {2,3,4,5}.(4.11) It has been shown [6] that, from all possible convergents of the expansion of y/2m, the convergent with the largest denominator smaller than Nis a good candidate of the ratio s/r with a probability of at least 4/π2≈40.5%, given that the following condition is satisfied y 2m−s r≤1 2r2.(4.12) 21 4.5. IMPLEMENTING MODULAR GATES Since the most likely value to measure yis the closest integer to 2ms/r, it follows that y−2ms r≤1 2−→ y 2m−s r≤1 2m+1 .(4.13) We have that r < N as discussed. By taking nas the length of bitstring N(in other words, the minimal number of bits required to represent N, i.e. n=⌊log2(N) + 1⌋), it follows that r < 2n, since 2n−1 is the largest n-bit integer. From here r < 2n→1 2r2>1 22n+1 .(4.14) This, together with Eq. 4.12, leads to m≥2n. From now on, the lowest valid qubit count of m= 2nwill be considered for QPF procedures unless stated otherwise, and n will always refer to the the length of bitstring N. Note that the qubit count qstill needs to be discussed, since it will depend on how the gate Ua,N is implemented. This post-processing may be classically done. However, the period finding procedure and post-processing discussed so far has caveats to be discussed. First of all, there will always be a likely measurement of value y= 0, corresponding to phase s= 0. Such a measurement provides no information as nothing can be extracted through continued fractions. Moreover, an unsuccessful measurement may be made. Since the success of the continued fraction post-processing relies on performing optimal measurements, post-processing unsuccessful measurements will lead to errors in the estimation of r. An additional and more subtle caveat to discuss corresponds to the case when s/r is reducible. In this cases, the discussed post-processing will yield a false positive: if s′/r′is the irreducible version, post-processing a good measurement will yield r′as the estimated order, which is not rbut merely some factors of it instead. In fact, since smight be any value between 0 and r−1, there is a relevant chance that sand rshare factors. Fortunately, the fact that r′is essentially rwithout a few factors can be exploited: if one happens to measure and extract more than one of these false positives, there is a decent chance that they together contain all the factors of r3, which can be checked by testing a value of rgiven by their least common multiple: r= lcm(r′ 1, r′ 2, . . . ) 4.5 Implementing modular gates Shor’s algorihm, as explained in the previous section, is rooted in the existence of a modNmultiplication unitary gate described in Eq. 4.7. There is not a unique construction of such a gate. But, in this work, a particular implementation is provided. The proposed implementation follows Ref. [7], constructing modular multiplication from modular addition and modular addition from regular addition. More precisely, given two integers aand xof bitstring length smaller or equal to n(in other words, both integers can be stored/represented with nbits), their mod-Nproduct (a·x) (mod N) may be expanded by using the binary expression of x(where x(j)corresponds to the j-th bit of 3As a matter of fact [3], there is at least a 25% chance that two values s′ 1and s′ 2share no common factors. In that case s1/r1and s2/r2were reduced by simplifying a different factor each, hence r′ 1and r′ 2 together contain all factors of r. 22 4.5. IMPLEMENTING MODULAR GATES x): a·x=a·20x(0) +a·21x(1) +···+a·2n−1x(n−1) , (a·x) (mod N)=(. . . ((20ax(0)) (mod N)+21ax(1)) (mod N)+ +···+ 2n−1ax(n−1)) (mod N). (4.15) 4.5.1 Adder gate The starting point of this implementation is therefore an adder gate, a gate whose action over a basis state encoding an integer |x⟩is to add a constant integer a, resulting in the basis state encoding |x+a⟩. There are several existing implementations of adder gates, but the adder gate used in this work follows Ref. [8] and it is described by the circuit in Fig. 4.4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a(q−1) a(q−2) . . . a(1) a(0) |˜x⟩(q−1) R1R2Rq−1Rq] x+aE(q−1) |˜x⟩(q−2) R1Rq−2Rq−1] x+aE(q−2) . . . |˜x⟩(1) R1P2] x+aE(1) |˜x⟩(0) R1] x+aE(0) ADDa Figure 4.4: Adder circuit implementation [8]ADDa, based on Fourier space, for a q-qubit register. The circuit has a size of O(q2), and a depth of O(q) since all phase gates Rjfor a fixed jcan be applied in paralell. Since ais known beforehand, the “controlled” phase gates are not really controlled: when the circuit is prepared for a, phase gates are only present for nonzero bits of a. This adder gate works on Fourier space. A QFT gate must be applied on a basis state before, which is denoted with a tilde: |ex⟩ ≡ QFT |x⟩, |x+a⟩=QFT−1ADDaQFT |x⟩.(4.16) By studying the top qubit |ex⟩(q−1), the effect of the P1...Pqrotations (conditioned on bits of a, thus equivalent to Pa(q−1) 1...Pa(0) qintroducing a total phase of ei2πa(q−1) 21+...+a(0) 2q= ei2π 2qa) shows how the adder works: |ex⟩(q−1) =1 √2(|0⟩+ei2πx 2q|1⟩)Pa(q−1) 1...Pa(0) q −−−−−−−−→ 1 √2(|0⟩+ei2πx+a 2q|1⟩) = ] x+aE(q−1) .(4.17) Since there may be underflow issues, n+ 1 qubits are actually needed for n-bit number addition. A subtraction (performed by an inverse adder gate) resulting in a negative integer −z(with z > 0) has a top qubit 1 √2|0⟩+ei2π−z 2n+1 |1⟩. The equivalent positive phase has a value of 2π−2π−z 2n+1 i.e. 2π2n+1−z 2n+1 . In fact, the subtraction result actually encodes the integer 2n+1 −z, which has the top (n+ 1)-th bit set due to underflow. 23 4.5. IMPLEMENTING MODULAR GATES 4.5.2 Modular adder gate In a similar fashion, a mod-Madder gate performs modular addition on the integer encoded by a basis state, transforming |x⟩into |(x+a) (mod N)⟩. Given a<Nand x<Nin a basis state, the circuit described in Fig. 4.5 performs modular addition provided a regular addition gate. . . . |˜x⟩(n) ADDaADD−1 NQFT−1QF T ADDNADD−1 aQFT−1 X X QFT ADDa ^ (x+a) (mod N)E(n) |˜x⟩(0) ^ (x+a) (mod N)E(0) |0⟩X X |0⟩ MADDa,N Nsubtraction check asubtraction check Figure 4.5: Mod-Nadder circuit implementation [7]MADDa,N . The circuit has a total of n+ 2 qubits, composed of an (n+ 1)-qubit register and an ancillary qubit. The circuit has a size of O(n2) and a depth of O(n) like the adder gate since it is composed of a constant number of QFT, adder and elementary gates. The requirements in aand xallow for a simple way to perform modular addition. Under this constraints x+a < 2N, so in order to work under mod-Narithmetics, at most N would need to be subtracted once (only if x+a≥N) aside from adding xand a. Therefore, the first half of the circuit is straightforward: ais added to xin the basis state, Nis subtracted and a check is performed on whether Nneeded to be subtracted in first place, adding Nback again otherwise. If the subtraction yielded a negative integer (when x+a<N), the extra qubit would be flipped by the controlled-Xgate (thus set to |1⟩) due to underflow. Note that this is essentially treating the bit encoded in the ancillary qubit as a Boolean value and storing whether x+a<N(1 if true or 0 if false). This leaves the top qubit register as the desired outcome of (x+a) (mod N). However, additional steps are required in order to set the ancillary qubit back to |0⟩, since this qubit will be in an unknown state depending on the specific values of xand a. The following modular arithmetics property is used: (x+a) (mod N)≥a⇔x+a < N . (4.18) The second half checks whether subtracting adoes not yield a negative number, thus whether (x+a) (mod N)≥a(note the Xgates before and after the control on the ancillary qubit, equivalent to working with the negated condition) adding aback again to keep the result intact in the top qubit register. The bit encoded in the ancillary qubit starts as 0, is then flipped if x+a<Nin the first half, and is flipped again if (x+a) (mod N)≥ain the second half. Due to Eq. 4.18, it inmediately follows that these conditions are actually the same (either both true or both false), hence flipping the bit two times or not flipping it at all and hence ensuring it is always |0⟩by the end of the circuit. 24 5.2. GROVER’S ALGORITHM Figure 5.5: Quantum counting algorithm (iQPE) simulation results for a list with N= 32 items of which the last M= 5 are target items, with a total of 10 cycles. Green bars correspond to optimal measurements. Both algorithm simulations, as expected, result in similar probability distributions. The two most likely integers to extract are t= 892 and t= 132 in both cases, corresponding to the closest integers to the phase, with the two next likely integers neighboring values t= 133 and t= 891. For both measured tintegers, a value of M= 4.967 is computed by Eq. 3.12, which is a great estimation of the target item count. For the second most-likely integer pair (t= 133 and t= 891) a value of M= 5.039 is computed, which is a very good estimation as well. Moreover, since Mis an integer, having to round the resulting estimation leads to even better odds of obtaining the right value as the error gets removed. For an arbitrary real value, this would not be the case. For comparison, an additional simulation is shown in Fig. 5.6 using a different amount of m= 5 phase estimation cycles. This and all following quantum counting simulations will be performed with iterative phase estimation routines, since they are equivalent but less memory intensive than regular phase estimation implementations. Figure 5.6: Quantum counting algorithm (iQPE) simulation results, for a list of N= 32 items of which the last M= 5 are target items, with a total of 5 cycles. Green bars correspond to optimal measurements. While the probability of optimal measurements improves, phases are extracted with less precision, which impacts the estimated count: following Eq. 3.12, a value of M= 4.686 is estimated for the two optimal measurements. In order to simulate larger lists of items, a list of N= 1024 items and M= 17 target 31 5.3. SHOR’S ALGORITHM items is studied in Fig. 5.7. Figure 5.7: Quantum counting algorithm (iQPE) simulation results, for a list with N= 1024 items of which the last M= 17 are target items, with a total of 5 cycles. Green bars correspond to optimal measurements. By Eq. 3.12, a value of M= 9.83 is obtained from the two optimal (and again the most likely) measurements, yielding a bad estimation of 10 = 17. Too little phase estimation cycles were used, and the phase was extracted with too small precision. 5.3 Shor’s algorithm With regards to the prime factorization problem, Shor’s algorithm was discussed, which relies on the Quantum Period Finding algorithm. The quantum algorithm is simulated for some examples, explaining in detail the classical post-processing needed for measurement results. Hence, we discuss an entire application of Shor’s algorithm for a given Nand some chosen group element a. The Quantum Period Finding routine is more demanding in both qubit requirement and circuit depth. The simplest integer typically factored is N= 15, i.e. n= 4, which in the discussed implementation would require 4n+ 2 = 18 qubits if performed with regular phase estimation and 2n+ 3 = 11 qubits with the iterative version. Since simulating 18 qubits is too memory intensive for the available computing resources, simulations will only be computed for iterative phase estimation versions. This is not a limitation whatsoever, since it has already been shown in previous simulations that the results are the same. As it was done with quantum counting simulations, QPF simulation results are displayed as probability estimations by collecting the measurement results of 1000 circuit simulations. False positives may be easily discarded without knowing the real order, since they must satisfy Eq. 4.1. The following steps of the algorithm would fail otherwise, yielding nonsense factors. Simulations of the Quantum Period Finding procedure for N= 15 and a= 4 are illustrated in Fig. 5.8. 32 5.3. SHOR’S ALGORITHM Figure 5.8: Quantum Period Finding (iQPE) simulation results for N= 15 with element a= 4. Green bars correspond to optimal measurements. This is a particularly nice case, where the corresponding phases 22ns/r are exact integers. Measuring y= 0 gives no information. Measuring y= 128 yields a fraction estimate y/22n= 128/256 = 1/2≡ {2}, whose post-processing is straightforward. There is a single convergent, and hence, an inmediate candidate order of r= 2, which is indeed the real order since 42≡1 (mod 15). The trivial case is not satisfied since 41+ 1 = 0 (mod N), and thus the factors of Nare straightforwardly obtained, p= gcd(41+ 1,15) = 5 , q = gcd(41−1,15) = 3 .(5.2) The case of N= 15 with a different group element (a= 2) is illustrated in Fig. 5.9. Figure 5.9: Quantum Period Finding (iQPE) simulation results for N= 15 with element a= 2. Green bars correspond to optimal measurements. This is another relatively simple case, but a particular measurement may cause trouble when post-processing as previously mentioned. If y= 128 (y/22n= 128/256 ≡ {2}) is measured, post-processing will be the same as the previous one performed for a= 4 and thus yield an order of r= 2. This turns out to be a false positive, since 22= 1 (mod 15) (the real order is r= 4). The phase corresponding to this measurement happens to be s/r = 2/4=1/2, a reducible ratio which makes the post-processing fail. Note that, nevertheless, a factor of the order is extracted, since 2 is a factor of the real order r= 4. A less simple result is obtained for N= 21 (i.e. n= 5) and a= 16, shown in Fig. 5.10. 33 5.3. SHOR’S ALGORITHM Figure 5.10: Quantum Period Finding (iQPE) simulation results for N= 21 with element a= 16. Green bars correspond to optimal measurements. In this case, there is a single optimal measurement corresponding to integer phase factors (y= 0); the other optimal measurements therefore are the closest integers. For instance, for a measurement of y= 683 (y/22n= 683/1024 ≡ {1,2,341}) the convergent {1,2} ≡ 2/3 has the largest denominator smaller than 21, from where a correct order of r= 3 is obtained. The order is odd, but factoring may succeed with the roots of a= 16 as previously discussed. For the square root a= 4, a trivial case is satisfied (43−1≡0 (mod 21)). The remaining root to check is a= 2, for which simulations of the Quantum Period Finding procedure are performed and showcased in Fig. 5.11. Figure 5.11: Quantum Period Finding (iQPE) simulation results for N= 21 with element a= 2. Green bars correspond to optimal measurements. Optimal measurements are the same as in the previous case. For a measurement of y= 171 (y/22n= 171/1024 ≡ {5,1,84,2}), post-processing yields a target convergent {5,1} ≡ 1/6, resulting in a (correct) order of r= 6: 26≡1 (mod 21). The trivial case is not satisfied (23+ 1 = 0 (mod 21)), and hence 21 is successfully factored, p= gcd(23+ 1,21) = 3 , q = gcd(23−1,21) = 7 .(5.3) Since measurements may not be optimal, let us check the case of an unsuccessful measurement of y= 601 (y/22n= 601/1024 ≡ {1,1,2,2,1,1,1,10,2}). Post-processing yields a target convergent {1,1,2,2,1} ≡ 10/17 and an estimation of r= 17, which can be discarded by checking that 217 = 1 (mod 21). As previously mentioned, the post-processing 34 5.3. SHOR’S ALGORITHM technique will produce garbage if applied to an unsuccessful measurement: a measurement of y= 299 estimates r= 17 as well, y= 707 estimates r= 13, y= 92 estimates r= 11. . . all of which can be checked to be invalid order candidates. Therefore, for the remaining algorithms only optimal measurements (if any) will be discussed. All simulations so far were performed using m= 2niterative phase estimation cycles. For comparison, this last case of N= 21 and a= 2 is now simulated with an atypical cycle count of m= 5 and shown in Fig. 5.12. Figure 5.12: Quantum Period Finding (iQPE) simulation results for N= 21 with element a= 2, with a cycle count of m= 5. Green bars correspond to optimal measurements. For measurements of y= 5 and y= 27, an incorrect order of r= 13 is estimated. For y= 11 and y= 21, an incorrect order of r= 3 is estimated. For y= 16, the case of a reducible s/r phase, an incorrect order of r= 2 is obtained. The same case may be simulated with an even lower cycle count of m= 3, whose results are displayed in Fig. 5.13. Figure 5.13: Quantum Period Finding (iQPE) simulation results for N= 21 with element a= 2, with a cycle count of m= 3. Green bars correspond to optimal measurements. From the 2m= 8 total measurable values, 6 (a majority of them) are optimal. For measurements of y= 1, y= 3, y= 5 and y= 7 an incorrect order of r= 8 is estimated. For y= 4, the case of a reducible s/r phase, an incorrect order of r= 2 is obtained. As seen so far with the different phase estimation-based algorithm results, lower m values imply a more limited range of potential measurements. Moreover, these results show the constraint imposed by the post-processing condition given by Eq. 4.12: for values smaller than m= 2n, the continued fractions-based procedure cannot guarantee 35 5.3. SHOR’S ALGORITHM that the correct order is encoded in a convergent, since the fraction y/2mwas obtained with too little precision. The remaining simulations will be just performed with m= 2n. Moving into larger integers to factor, simulations for N= 33 (i.e. n= 6) and a= 5 are displayed in Fig. 5.14. Figure 5.14: Quantum Period Finding (iQPE) simulation results for N= 33 with element a= 5. Green bars correspond to optimal measurements. For instance, for an optimal measurement of y= 1229 (y/22n= 1229/4096 ≡ {3,3,204,2}) the correct order of r= 10 is obtained. Additional simulation results for larger values are compiled below: for N= 39 (i.e. n= 6) and a= 7 in Fig. 5.15;N= 51 (i.e. n= 6) and a= 5 in Fig. 5.16;N= 55 (i.e. n= 6) and a= 7 in Fig. 5.17; and N= 77 (i.e. n= 7) and a= 5 in Fig. 5.18. Figure 5.15: Quantum Period Finding (iQPE) simulation results for N= 39 with element a= 7. Green bars correspond to optimal measurements. 36 5.3. SHOR’S ALGORITHM Figure 5.16: Quantum Period Finding (iQPE) simulation results for N= 51 with element a= 5. Green bars correspond to optimal measurements. Figure 5.17: Quantum Period Finding (iQPE) simulation results for N= 55 with element a= 7. Green bars correspond to optimal measurements. Figure 5.18: Quantum Period Finding (iQPE) simulation results for N= 77 with element a= 5. Green bars correspond to optimal measurements. 37 Chapter 6 Conclusion In this work, theoretical descriptions of two widely known quantum algorithms are given, followed by simulations of the algorithms illustrating key concepts of their implementations, how they work in practice and how the desired output is obtained by post-processing quantum measurements. It has been suggested why they are more efficient than their classical counterparts, despite their probabilistic nature instead of guaranteeing results like the classical versions. From a physical point of view, these algorithms consist of adequate combinations of unitary actions on multiple two-dimensional quantum mechanical systems, along with some classical pre-processing and post-processing. The discussed algorithms cleverly take advantage of unique properties of quantum mechanics. Superposition is an indispensable property, virtually present from the very beginning in all discussed algorithms: all of them start by constructing an equiprobable superposition of basis states, and operate by transforming the superposition creating destructive interferences, finally yielding a system state where a final measurement will extract some desired information with decent probability. In Grover’s algorithm, the Grover iteration transforms the initial superposition state step by step. After the right amount of iterations, the non-target state amplitudes get almost collapsed, while the desired target amplitudes are amplified as much as possible. In the other two, QPE-based algorithms, the final inverse QFT gate nearly collapses all basis state amplitudes not containing binary encodings of some phase factor, so that a measurement will result in a close integer to one of those factors with high probability. This work served as an introduction to quantum computing and, specially, to the quantum circuit model. All algorithms were explained in detail and manually implemented through Qiskit, a state-of-the-art and widely used framework for implementing quantum algorithms. Such a hands-in implementation of the algorithms gave me a great notion of how each of their internal parts work. The source code is available in the repository of the University of the Basque Country (ADDI). 38 Bibliography [1] “40 years of quantum computing,” Nature Reviews Physics, vol. 4, no. 1, pp. 1–1, 2022. [2] A. Kay, Tutorial on the quantikz package, 2023. [Online]. Available: https://osl. ugr.es/CTAN/graphics/pgf/contrib/quantikz/quantikz.pdf. [3] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information. Cambridge University Press, 2010. [4] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM review, vol. 41, no. 2, pp. 303–332, 1999. [5] T. Lawson, “Odd orders in shor’s factoring algorithm,” Quantum Information Processing, vol. 14, pp. 831–838, 2015. [6] J. Barzen and F. Leymann, “Continued fractions and probability estimations in shor’s algorithm: A detailed and self-contained treatise,” AppliedMath, vol. 2, no. 3, pp. 393– 432, 2022. [7] S. Beauregard, Circuit for shor’s algorithm using 2n+3 qubits, 2003. [8] T. G. Draper, Addition on a quantum computer, 2000. arXiv: quant-ph/0008033. [9] A. Javadi-Abhari, M. Treinish, K. Krsulich, et al.,Quantum computing with qiskit, 2024. arXiv: 2405.08810. 39