Automatic generation of efficient oracles: The less-than case

Contents lists available at ScienceDirect The Journal of Systems & Software journal homepage: www.elsevier.com/locate/jss Automatic generation of efficient oracles: The less-than case✩ Javier Sanchez-Rivero a,Daniel Talaván b,Jose Garcia-Alonso c,∗,Antonio Ruiz-Cortés d,Juan Manuel Murillo b,c aUniversidad de Sevilla, Seville, Spain bCOMPUTAEX, Cáceres, Spain cUniversidad de Extremadura, Cáceres, Spain dSCORE Lab, I3US Institute, Universidad de Sevilla, Seville, Spain ARTICLE INFO Dataset link:https://github.com/JSRivero/Less -than-oracle Keywords: Quantum computing Grover’s algorithm Amplitude Amplification Oracle automatic generation Qiskit Efficiency ABSTRACT Grover’s algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence faster than any classical algorithm. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. A generalisation of it is the oracle for Amplitude Amplification, that marks multiple desired states. In this work we present a classical algorithm that builds a phase-marking oracle for Amplitude Amplification. This oracle performs a less-than operation, marking states representing natural numbers smaller than a given one. Results of both simulations and experiments are shown to prove its functionality. This less-than oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with the one generated by Qiskit automatic method, Diagonal. We show that the depth of our less-than oracle implementation is always lower. In addition, a comparison with another method for oracle generation in terms of gate count is also conducted to prove the efficiency of our method. The result presented here is part of a research work that aims to achieve reusable quantum operations that can be composed to perform more complex ones. The final aim is to provide Quantum Developers with tools that can be easily integrated in their programs/circuits. 1. Introduction We are currently on the noisy intermediate-scale quantum (NISQ) era (Preskill,2018) where quantum computers with several qubits (quantum bits) are available (Zhu et al.,2022;Huang et al.,2020;Wang et al.,2018). This has enabled quantum software developers to test the theoretical work on quantum algorithms on real devices (Figgatt et al.,2017;Vandersypen et al.,2001). This has motivated a significant research effort devoted to the optimisation of existing quantum algorithms and the creation of new ones. Quantum algorithms try to leverage the quantum properties of qubits to reach a final quantum state where some of the states have increased amplitude. These states are the most probable solution to the problem being addressed. The possibility of having superposition states and the way amplitudes are manipulated means that certain problems can be solved more efficiently by quantum computers than by classical ones (Vandersypen et al.,2001;Cerezo et al.,2021). A well-known example of this is Grover’s algorithm. ✩Editor: Raffaela Mirandola. ∗Corresponding author. E-mail address: [email protected] (J. Garcia-Alonso). Grover presented (Grover,1996) a quantum algorithm that searches in an unordered sequence faster than any known classical algorithm. This algorithm works by combining two quantum operations. First, it marks (by giving it a 𝜋-phase) the desired quantum state. This marking operation is known as oracle. Then, the second operation aims to amplify the amplitude of the marked state. This operation is called diffusion operator or diffuser. In order to reach such amplification it is often needed to repeat the pair oracle-diffuser several times. The generalisation of Grover to amplify multiple states is known as Amplitude Amplification (AA) (Brassard et al.,2002;Grover,1998). In this paper we present an algorithm for the automatic generation of oracles that perform a less-than operation. Taking as input a quantum state in which qubits encode natural numbers (including 0), this oracle gives a 𝜋-phase to those numbers less than a given one. The complete less-than operation is applied using this oracle in Grover’s algorithm. Its complexity function is (√𝑁∕𝑀), where 𝑁is the number of naturals encoded in the quantum state and 𝑀(1≤𝑀 < 𝑁) is the number of naturals less than the given number. https://doi.org/10.1016/j.jss.2024.112203 Received 30 September 2023; Received in revised form 30 July 2024; Accepted 29 August 2024 The Journal of Systems and Software 219 (2025) 112203 Available online 4 September 2024 0164-1212/© 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/bync-nd/4.0/ ). J. Sanchez-Rivero et al. Thus, the complexity function is bounded above by (√𝑁)(better than classical (𝑁)for an unordered sequence of naturals). Moreover, the provided implementation avoids the use of ancilla qubits. The result presented here is part of a research work that aims to achieve reusable and composable quantum operations. For example, from the less-than oracle, a greater-than oracle can be easily obtained, and by combining both, ranges of integers can also be produced. The rest of the paper is organised as follows. Next, in Section 2, the background of this work is provided. Then, a detailed description of the classical algorithm for the automatic generation of the lessthan implementation is presented in Section 3. A formal proof that the generated implementation actually marks the desired states is shown in 4. Results of simulations and experiments on real quantum hardware are discussed on Section 5. A study of the efficiency of the oracle and comparisons with other methods are provided in Section 6. Finally, the conclusions and future work are presented in Section 7. A previous version of this work was originally presented as a conference paper (Sanchez-Rivero et al.,2023). In this document we have added the formal proof of the oracle’s correctness on Section 4. The implementation of multi-qubits gates is changed to the linear-growth from da Silva and Park (2022) and in consequence the experiments and simulations have all been repeated. Section 6has been completely updated to compare versus Qiskit’s best method and versus the Phase-tolerant method presented in Seidel et al. (2023). 2. Background 2.1. Gate-based quantum-computing A quantum logic gate is each operation performed on the quantum circuit, analogous to the classical logic gates. Mathematically, each gate is represented by a 2𝑛× 2𝑛unitary matrix where 𝑛is the number of qubits and 𝑁= 2𝑛states which form an orthonormal basis. The action of a gate on a specific quantum system is determined by multiplying the state vector by the matrix representation of the gate (Nielsen and Chuang,2000). The state vector represents the amplitude of the quantum states of the system. The probability of measuring one given state in the computational basis is given by the squared modulus of the amplitude associated with that state. To illustrate these concepts, consider a quantum system with two qubits. The state vector 𝝍for such a system in the computational basis might be represented as: 𝝍=⎛⎜⎜⎜⎜⎝ 𝑐00 𝑐01 𝑐10 𝑐11 ⎞⎟⎟⎟⎟⎠ =(𝑐00 𝑐01 𝑐10 𝑐11)𝑇 where each 𝑐𝑖𝑗 represents the amplitude associated with the basis state |𝑖𝑗⟩. In this context, the basis states |00⟩,|01⟩,|10⟩, and |11⟩for a four-state orthonormal basis. For example, if the system is in the state 𝜓= (1000)𝑇, this means that the amplitudes are 1for the state |00⟩ and 0for the remaining states |01⟩,|10⟩and |11⟩, and consequently, the probabilities of measuring each state in the computational basis are given by the squared modulus of the respective amplitudes. In this case |1|2= 1 for state |00⟩and |0|2= 0 for the remaining states. Thus, the system has a 100% chance of being measured in the state |00⟩and no chance of being measured in the states |01⟩,|10⟩, or |11⟩. Let now consider the application of the X gate, which for a single qubit is represented by the matrix: 𝑋=(0 1 1 0) To apply the X gate to both qubits in a two-qubit system, we need to use the tensor product of the X gate with itself. This is because the tensor product allows us to construct a matrix that operates on the combined state space of both qubits. The combined operation for applying the X gate to both qubits is: 𝑋 ⊗ 𝑋 =⎛⎜⎜⎜⎜⎝ 0001 0010 0100 1000 ⎞⎟⎟⎟⎟⎠ Applying this operation to the initial state vector 𝝍: 𝝍′=⎛⎜⎜⎜⎜⎝ 0001 0010 0100 1000 ⎞⎟⎟⎟⎟⎠ ⎛⎜⎜⎜⎜⎝ 1 0 0 0 ⎞⎟⎟⎟⎟⎠ =⎛⎜⎜⎜⎜⎝ 0 0 0 1 ⎞⎟⎟⎟⎟⎠ This means that the new probabilities of measuring each state are: |0|2= 0 for states |00⟩,|01⟩and |10⟩, and |1|2= 1 for state |11⟩. Thus, after applying the X gate to both qubits, the system has a 100% chance of being measured in the state |11⟩, with no chance of being measured in the other states. 2.2. Oracles The oracle has been identified as a pattern for quantum algorithms (Leymann,2019). An oracle can be thought as a black box performing a function that is used as an input by another algorithm (Liu and Zhou,2021). Thus, how an oracle works is not a matter of concern for the algorithm that uses it. These features make oracles a good tool for quantum software reuse. Apart from Grover’s, many other algorithms employ oracles. Some well known examples are Deutsch and Jozsa (1992), Simon (1997) or Bernstein and Vazirani (1997). There are two main types of oracles described in the literature (Gilyén et al.,2019), probability oracles and phase oracles. On one hand, probability oracles are common in quantum optimisation procedures and encode a function in the amplitude of the quantum states. On the other hand, phase oracles are used in quantum algorithms (such as Grover’s) and encode a function in the phase of the quantum states. In the case of Grover’s algorithm, the function implemented by the oracle recognises the desired states. As mentioned above, the less-than oracle developed in this work is a phase oracle. Thinking of oracles in terms of black boxes favours the reusability of quantum software. One would then expect any reusable software to have the best possible quality attributes. Today’s quantum devices are subject to decoherence. Thus, the depth of the circuits is a key aspect to maximise their reliability. The greater the depth of a circuit, the more it is exposed to decoherence and the lower its reliability (Saki et al.,2019). Therefore, if the depth of the circuit that implements a quantum algorithm is not taken into account, it can end up producing a result that is indistinguishable from pure noise (Preskill,2018). So keeping depth of oracles optimised, contributes to optimise their quality attributes and their chance to be reused. To reduce the depth of the less-than oracle, the linear-depth multicontrolled gate proposed in da Silva and Park (2022) is reused as a piece of existing quantum software. The depth of this gate scales linearly on the number of qubits, improving the polynomial growth of previous implementations. It does not require any ancilla qubits and outperforms Qiskit (tA v et al.,2021) implementation from five qubits onwards. In addition, results show that the linear-depth multicontrolled gate is useful on NISQ devices and improves the accuracy of results. In order to properly contextualise the depth of the circuit associated to the oracle proposed in this paper, we compare it to Diagonal, a method implemented in Qiskit (tA v et al.,2021) which automatically generates an implementation of an oracle provided its matrix (Diagonal Gate,2020). This Diagonal method is based on (Shende et al.,2004). There are other automatic methods for oracle generation, such as Seidel et al. (2023). However, as Qiskit is one of the most used quantum The Journal of Systems & Software 219 (2025) 112203 2 J. Sanchez-Rivero et al. SDKs, we have chosen to compare the performance of the less-than implementation with the Diagonal generated circuit. Besides depth, the type of gates is also key in the reliable execution of quantum circuits (Lee et al.,2006) as precision differs from one gate to another. A gate count comparison is also conducted comparing our method with both Diagonal method from Qiskit and Phase Tolerant method from Seidel et al. (2023). In this paper not only the concept of the oracle is provided, also a classical algorithm is detailed to automatically generate an efficient implementation of the proposed less-than oracle. This algorithm could be included as a pattern for the less-than problem in intelligent code generators such as the one mentioned in Gemeinhardt et al. (2021). 3. Algorithm for the automatic generation of the oracle In this section we detail the classical algorithm designed to automate the building of the oracle circuit. This oracle will mark with a 𝜋-phase all quantum states which represent natural numbers strictly smaller than a given one. The oracle is represented by a unitary matrix of the form: ⎛⎜⎜⎜⎜⎜⎜⎝ −1 ⋱ −1 0 1 ⋱ 0 1 ⎞⎟⎟⎟⎟⎟⎟⎠ (1) where the matrix have 2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 ×2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 elements, being 𝑛𝑞𝑢𝑏𝑖𝑡𝑠 the number of qubits. The diagonal thus has 2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 elements. The diagonal has a number of −1s equal to 𝑚and a number of 1s equal to 2𝑛𝑞𝑢𝑏𝑖𝑡𝑠 −𝑚, where 𝑚is the threshold integer. The classical algorithm we propose is based on the idea that, in order to compare the binary representation of two natural numbers 𝑛1and 𝑛2, it is needed to look for the first bit (starting at the most significant one) which differs in these two numbers. Once this bit is found, it is compared for the two numbers, the one whose bit is 0is the smaller one. E.g. when comparing1𝑛1= 1112= 7 and 𝑛2= 1012= 5, the most significant bits are both equal to 1, the second most significant bits differ. The bit which is 0 belongs to 𝑛2, hence 𝑛2is the smaller one. Algorithm 1shows the pseudocode of this algorithm. The quantum circuit generated by this algorithm can be found in the next section in Eq. (8). The algorithm consists of four steps, tagged in the pseudocode. The first part is obtaining the binary expression of 𝑚. Secondly, a 𝜋-phase is given depending on the most significant bit, by means of the operator 𝑉. The third step is giving a 𝜋-phase to the remaining bits, values of the index 𝑖from 𝑛−2 to 0, by the operators 𝑈𝑖. Last step is returning the qubits corresponding to bits equal to 0 to the original state by means of 𝑋gates. The algorithm needs as inputs the number of qubits 𝑛and a natural number 𝑚where 0< 𝑚 < 2𝑛. As stated before, the output of our algorithm produces a quantum circuit with 𝑛qubits which gives a 𝜋phase to all states representing natural numbers strictly smaller than 𝑚. The first step of the algorithm is converting the number 𝑚to binary form, 𝑚binary =𝑏𝑛−1 …𝑏0, with 𝑛bits.2This is always possible because 𝑚 < 2𝑛. After that, it proceeds to check the first bit (most significant) of 𝑚binary,𝑏𝑛−1. If it is 1, hence 𝑚≥2𝑛−1, then the gates 𝑋𝑍𝑋 are applied to the qubit 𝑞𝑛−1 of the quantum circuit (2). This gives a 𝜋-phase to the 1In numbers like 1012the 2 in the subindex means that it is a binary number. 2In the case 𝑛= 4 and 𝑚= 3, the binary form would be 𝑚binary = 0011. states of the form |0𝑞𝑛−2 …𝑞0⟩, which represent numbers smaller than 2𝑛−1, thus smaller than 𝑚. 𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1)|𝑞𝑛−1 …𝑞0⟩= −𝛼0|0𝑞𝑛−2 …𝑞0⟩+𝛼1|1𝑞𝑛−2 …𝑞0⟩(2) where 𝛼0and 𝛼1are the amplitudes of the state |0𝑞𝑛−2 …𝑞0⟩and |1𝑞𝑛−2 …𝑞0⟩respectively, i.e. |𝛼0|2+|𝛼1|2= 1, and 𝐼⊗(𝑛−1) is the identity gate applied to the 𝑛− 1 least significant qubits. Algorithm 1: Less-than oracle classical builder Input: Number of qubits 𝑛and a natural number 𝑚where 0<𝑚<2𝑛 Output: Quantum Circuit which gives a 𝜋-phase to all states representing binary forms of natural numbers smaller than 𝑚 /* Binary expression of 𝑚*/; 𝑚binary ←binary(𝑚); 𝑄𝑢𝑎𝑛𝑡𝑢𝑚𝐶𝑖𝑟𝑐𝑢𝑖𝑡 ←Circuit of 𝑛qubits; 𝑏𝑛−1 ←1st bit (most significant) of 𝑚binary; /* 𝑉operator */; if 𝑏𝑛−1 = 0 then 𝑋gate to 𝑞𝑛−1; else 𝑋gate to 𝑞𝑛−1; 𝑍gate to 𝑞𝑛−1; 𝑋gate to 𝑞𝑛−1; end /* 𝑈𝑖operator */; for 𝑖←𝑛− 2 to 0do 𝑏𝑖←𝑖-th bit of 𝑚binary; 𝑞𝑖←𝑖-th qubit of 𝑄𝑢𝑎𝑛𝑡𝑢𝑚𝐶𝑖𝑟𝑐𝑢𝑖𝑡; if 𝑏𝑖= 0 then 𝑋gate to 𝑞𝑖; else 𝑋gate to 𝑞𝑖; 𝐶⊗(𝑛−𝑖−1)𝑍gate to qubits 𝑞𝑛−1,…, 𝑞𝑖; 𝑋gate to 𝑞𝑖; end end /* 𝑋⊗𝑀0operator */; for 𝑖←0to 𝑛− 1 do if 𝑏𝑖= 0 then 𝑋gate to 𝑞𝑖; end end Else, if 𝑏𝑛−1 is 0, an 𝑋gate is applied to 𝑞𝑛−1, which will be reversed at the end of the circuit, 𝑋 ⊗𝐼⊗(𝑛−1). Therefore, the operator regarding 𝑏𝑛−1 is the following: 𝑉=𝛿𝑏𝑛−11(𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1))+𝛿𝑏𝑛−10(𝑋 ⊗ 𝐼⊗(𝑛−1))(3) The following operator follows the same pattern for the remainder positions, 𝑖∈ {𝑛− 2,…,0}. If 𝑏𝑖is 0, an X gate is applied to 𝑞𝑖, 𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖). In case 𝑏𝑖is 1, the gates (𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)(4) are applied to {𝑞𝑛−1,…, 𝑞𝑖}. This gives a 𝜋-phase to the states |𝑏𝑛−1 …𝑏𝑖+1 0𝑞𝑖−1 …𝑞0⟩. As explained before, if the 𝑖th bit of 𝑚binary is 1, all numbers with 0 in the 𝑖th bit and the same 𝑛−𝑖− 1 first bits as 𝑚binary (𝑏𝑛−1 …𝑏𝑖+1) are smaller than 𝑚. The operator regarding 𝑏𝑖is the following: 𝑈𝑖=𝛿𝑏𝑖1((𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋))⊗ 𝐼⊗(𝑖) +𝛿𝑏𝑖0(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖))(5) The Journal of Systems & Software 219 (2025) 112203 3 J. Sanchez-Rivero et al. Fig. 1. Oracle generated taking 𝑚= 11 = 10112with 4 qubits. Finally, an 𝑋gate is applied to each 𝑞𝑖such that 𝑏𝑖= 0, 𝑛−1 ∏ 𝑖=0 ∶ 𝑏𝑖=0 𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖)(6) This is done because another 𝑋gate was applied to them in previous steps of the algorithm, so operation (6) returns these qubits to the initial state, except for a possible 𝜋-phase. Let 𝑀0= {𝑖∈ [0,…, 𝑛−1] |𝑏𝑖= 0 ∀𝑏𝑖∈𝑚binary}, then we denote the operator in Eq. (6) as 𝑋⊗𝑀0. Thus, the less-than oracle can be formally written as: 𝑉⋅(𝑛−2 ∏ 𝑖=0 𝑈𝑖)⋅𝑋⊗𝑀0(7) As an illustrative example of the algorithm output, we show the oracle generated taking 𝑚= 11 = 10112in Fig. 1. It can be observed that the quantum circuit generated by Algorithm 1does not require ancilla qubits to work as intended. The only part of the generated oracle whose depth could be reduced by the inclusion of ancilla qubits are the multi-controlled gates. However, for these gates we use the implementation described in da Silva and Park (2022) that does not include the use of ancilla qubits for depth reduction. Not requiring ancilla qubits allows the use of all available qubits for encoding the natural numbers. From this point, the implementation of the greater-than oracle mentioned above is trivial. Even more, the oracles greater-than and less-than can be composed in a way that, by combining them, we obtain ranges of integers. This oracle is obtained regardless of the order the greater-than and less-than oracles are applied, so they fulfil the commutative property. Moreover, they can be grouped in different oracles obtaining the same result. For instance, if we apply a lessthan oracle and a greater-than (which become a range) and afterwards another less-than oracle is applied, the final result is the same as if a less-than oracle is applied and, after that, a range of integers (greaterthan and a less-than oracles) is applied. This can be understood as the associative property of the oracles. Although this aspect is not exploited in this work it is one of the key motivations behind it. These combinations and further examples of less-than oracles may be found in the repository included in Code and Data. 3.1. Algorithm’s time complexity and circuit’s complexity The algorithm’s time complexity derives directly from the pseudocode 1of the algorithm. There are only two for loops from 0 to 𝑛, which are (𝑛). Inside one of those, at each iteration 𝑘∈ [1,…, 𝑛], a gate 𝐶𝑘𝑍is constructed, which is (𝑘). Therefore, time complexity of the classical algorithm is (𝑛2). Regarding the quantum circuit generated, its complexity is the depth of the circuit by the definition of depth (Nielsen and Chuang, 2000). This is analysed in depth in Section 6. 4. Mathematical proof of the oracle’s correctness Proposition 1. Let 𝑚be a non-negative integer, 𝑚∈Z,𝑚 > 0. Let 𝑛be an integer such that 2𝑛> 𝑚. Let 𝑚binary =𝑏𝑛−1 …𝑏0be its binary form with 𝑛bits. Let the oracle be the next set of gates: 𝑉⋅(𝑛−2 ∏ 𝑖=0 𝑈𝑖)⋅𝑋⊗𝑀0(8) where •𝑀𝑘is the set of indices of bits of 𝑚binary whose value is 𝑘∈ {0,1}. In the case of 𝑀0, it is formed by the positions of the 0s in 𝑚binary. Formally: 𝑀𝑘= {𝑖|𝑏𝑖=𝑘∀𝑏𝑖∈𝑚binary} •𝑋⊗𝑀0is an operator which applies an 𝑋gate to those qubits 𝑞𝑖such that 𝑏𝑖∈𝑀0, i.e, 𝑏𝑖= 0. Formally: 𝑋⊗𝑀0=∏ 𝑖∈𝑀0 𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖) •𝑉is the operator which applies an 𝑋gate to 𝑞𝑛−1 if 𝑏𝑛−1 = 0 and the gates 𝑋𝑍𝑋 to 𝑞𝑛−1 if 𝑏𝑛−1 = 1. Formally it can be written as follows: 𝑉=𝛿𝑏𝑛−11(𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1))+𝛿𝑏𝑛−10(𝑋 ⊗ 𝐼⊗(𝑛−1)) where 𝛿𝑖𝑗 is the Kronecker delta. •𝑈𝑖,0< 𝑖 < 𝑛 − 1, is the following operator: 𝑈𝑖=𝛿𝑏𝑖1((𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋))⊗ 𝐼⊗(𝑖) +𝛿𝑏𝑖0(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖)) The oracle (8) gives a 𝜋-phase to all states which represent a natural number smaller than 𝑚. Proof. The proof follows the next order: First, we prove that |0⟩is always marked (it represents the 0 hence it is always smaller than 𝑚 > 0). Then we take two digits 𝑏𝑖, 𝑏𝑗in 𝑚binary,𝑖<𝑗, such that 𝑏𝑖=𝑏𝑗= 1 and 𝑏𝑘= 0 for every 𝑘between 𝑖and 𝑗, i.e, 𝑏𝑖and 𝑏𝑗 are consecutive 1s in 𝑚binary. And we prove that the operators 𝑈𝑖and 𝑈𝑗, corresponding to 𝑏𝑖and 𝑏𝑗, give a 𝜋-phase to consecutive states, i.e., states which represent consecutive integers. Finally, we prove that the number of states marked are 𝑚. Let 𝑏𝑛−1 be the most significant bit of 𝑚binary. Because of hypothesis, 𝑚binary can be written with 𝑛bits. In case fewer bits are needed, the most significant bits not used are 0. The binary decomposition of 𝑚is: 𝑚= 𝑛−1 ∑ 𝑖=0 𝑏𝑖⋅2𝑖(9) Let us focus on the most significant bit, 𝑏𝑛−1, first. If 𝑏𝑛−1 = 1 ⇒𝑚≥ 2𝑛−1, then the operator 𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1) is 𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1)|𝑞𝑛−1 …𝑞0⟩= −𝛼0|0𝑞𝑛−2 …𝑞0⟩+𝛼1|1𝑞𝑛−2 …𝑞0⟩ where 𝛼0and 𝛼1are the amplitudes of the state |0𝑞𝑛−2 …𝑞0⟩and |1𝑞𝑛−2 …𝑞0⟩respectively, i.e. |𝛼0|2+|𝛼1|2= 1. The Journal of Systems & Software 219 (2025) 112203 4 J. Sanchez-Rivero et al. This gives a 𝜋-phase to all the states representing numbers strictly smaller than 2𝑛−1, namely state |0⟩. In case 𝑏𝑛−1 = 0, an X gate is applied. So the operator 𝑉corresponding to 𝑏𝑛−1, which is applied in the first place, is: 𝑉=1{𝑏𝑛−1=1}𝑋𝑍𝑋 ⊗ 𝐼⊗(𝑛−1) +1{𝑏𝑛−1=0}𝑋 ⊗ 𝐼⊗(𝑛−1) Let 𝑏𝑘be the first bit equals to 1, so 𝑏𝑙= 0 for all 𝑘<𝑙≤𝑛− 1. Then, all operators applied up to this point, 𝑉 , 𝑈𝑛−2,…, 𝑈𝑘+1, 𝑈𝑘3are as it follows: 𝑉⋅𝑈𝑛−2 ⋯𝑈𝑘+1 ⋅𝑈𝑘=(𝑋(𝑛−1−𝑘)⊗ 𝐼(𝑘+1))⊗ 𝑈𝑘(10) where 𝑈𝑘=(𝐼⊗(𝑛−𝑘−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑘−1)𝑍⋅(𝐼⊗(𝑛−𝑘−1) ⊗ 𝑋)⊗ 𝐼⊗(𝑘)(11) as 𝑏𝑘= 1. The operator described in (10) gives a 𝜋-phase to the states which follow the next pattern: |𝑏𝑛−1𝑏𝑛−2 …𝑏𝑘+1 0𝑞𝑘−1 …𝑞0⟩=|0 0 … 0 𝑞𝑘−1 …𝑞0⟩ This ranges between the states |𝛼𝑘⟩=|𝑏𝑛−1 …𝑏𝑘+1 0 0 … 0⟩=|00…00⟩ |𝛽𝑘⟩=|𝑏𝑛−1 …𝑏𝑘+1 0 1 … 1⟩=|0 … 0 0 ⏟⏟⏟ 𝑘th 1 … 1⟩ where 𝛼𝑘= 0 𝛽𝑘= 𝑘−1 ∑ 𝑙=1 2𝑙−1 Between these two states, including them as well, there are the following number of states: 𝑛[𝛼𝑘,𝛽𝑘]=𝛽𝑘−𝛼𝑘+ 1 = 𝑘−1 ∑ 𝑙=1 2𝑙−1 + 1 = 2𝑘−1 The matrix associated with operator (10) is a diagonal matrix with 0s outside of the main diagonal: diag{−1,…,−1 ⏟⏟⏟ 𝛽𝑘 ,1,…,1} This part of the proof has provided a comprehension of the first operator and proved that state |0⟩is in fact marked with a 𝜋-phase regardless of 𝑚. Next, we are going to prove that, provided two consecutive bits equal to 1 in 𝑚binary,𝑏𝑖and 𝑏𝑗, i.e. 𝑏𝑙= 0 for 𝑖 < 𝑙 < 𝑗,𝑈𝑖and 𝑈𝑗 give a 𝜋-phase to consecutive states.4 Let 𝑘<𝑖<𝑛if 𝑏𝑛−1 = 0 or 2≤𝑖<𝑛if 𝑏𝑛−1 = 1. In case 𝑏𝑖= 0, an 𝑋gate is applied to qubit 𝑞𝑖, which will be cancelled by another 𝑋gate at the end of the circuit, which would be equivalent to applying an identity gate 𝐼. Otherwise, if 𝑏𝑖= 1, the operator (𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)is applied (as in (11)). The combination of both cases is the operator 𝑈𝑖: 𝑈𝑖=𝛿𝑏𝑖1((𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋)⋅𝐶⊗(𝑛−𝑖−1)𝑍⋅(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋))⊗ 𝐼⊗(𝑖) +𝛿𝑏𝑖0(𝐼⊗(𝑛−𝑖−1) ⊗ 𝑋 ⊗ 𝐼⊗(𝑖)) We follow now the same reasoning as in the first part. Operator 𝑈𝑖 gives a 𝜋-phase to the states which follow the next pattern: |𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖+1 0𝑞𝑖−1 …𝑞0⟩ 3Plus the last 𝑋gates applied at the end to qubits corresponding to bits equal to 0, operator 𝑋⊗𝑀0, in this case on 𝑞𝑛−1, 𝑞𝑛−2 …, 𝑞𝑘+1. 4Note that 𝑈𝑙introduce no phase to any qubit, by definition of the operator 𝑈𝑖, as 𝑏𝑙= 0. This ranges between the states |𝛼𝑖⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖+1 0 0 … 0⟩ |𝛽𝑖⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖+1 0 1 … 1⟩ where 𝛼𝑖= 𝑛 ∑ 𝑙=𝑖+1 𝛿𝑏𝑙1⋅2𝑙−1 𝛽𝑖= 𝑛 ∑ 𝑙=𝑖+1 𝛿𝑏𝑙1⋅2𝑙−1 + 𝑖−1 ∑ 𝑙=1 2𝑙−1 Between these two states, including them as well, there are this number of states: 𝑛[𝛼𝑖,𝛽𝑖]=𝛽𝑖−𝛼𝑖+ 1 = 𝑛 ∑ 𝑙=𝑖+1 𝛿𝑏𝑙1⋅2𝑙−1 + 𝑖−1 ∑ 𝑙=1 2𝑙−1 − 𝑛 ∑ 𝑙=𝑖+1 𝛿𝑏𝑙1⋅2𝑙−1 + 1 = 𝑖−1 ∑ 𝑙=1 2𝑙−1 + 1 = 2𝑖−1 The matrix associated with operator 𝑈𝑖is: diag{1,…,1,−1 ⏟⏟⏟ 𝛼𝑖 ,…,−1 ⏟⏟⏟ 𝛽𝑖 ,1,…,1} Let 𝑗 < 𝑖 be the next index such that 𝑏𝑗= 1 and there are no bits equal to 1 between 𝑏𝑖and 𝑏𝑗, i.e. 𝑏𝑙= 0 for 𝑖<𝑙<𝑗. Then we see that |𝛼𝑗⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖…𝑏𝑗+1 0 0 … 0⟩ =|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖0 … 0 0 ⏟⏟⏟ 𝑗th 0 … 0⟩ |𝛽𝑗⟩=|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖…𝑏𝑗+1 0 1 … 1⟩ =|𝑏𝑛−1𝑏𝑛−2 …𝑏𝑖0 … 0 0 ⏟⏟⏟ 𝑗th 1 … 1⟩ are extremes of the interval containing the states 𝑈𝑗gives a 𝜋-phase to. Moreover, 𝛼𝑗= 𝑛 ∑ 𝑙=𝑗+1 𝛿𝑏𝑙1⋅2𝑙−1 = 𝑛 ∑ 𝑙=𝑖 𝛿𝑏𝑙1⋅2𝑙−1 𝛽𝑖= 𝑛 ∑ 𝑙=𝑗+1 𝛿𝑏𝑙1⋅2𝑙−1 + 𝑗−1 ∑ 𝑙=1 2𝑙−1 = 𝑛 ∑ 𝑙=𝑖 𝛿𝑏𝑙1⋅2𝑙−1 + 𝑗−1 ∑ 𝑙=1 2𝑙−1 where we have used that 𝑏𝑖= 1 and 𝑏𝑖−1,…, 𝑏𝑗+1 are 0. It can be noted that: 𝛽𝑖+1 = 𝑛 ∑ 𝑙=𝑖+1 𝛿𝑏𝑙1⋅2𝑙−1+ 𝑖−1 ∑ 𝑙=1 2𝑙−1+1 = 𝑛 ∑ 𝑙=𝑖+1 𝛿𝑏𝑙1⋅2𝑙−1+2𝑖−1 = 𝑛 ∑ 𝑙=𝑖 𝛿𝑏𝑙1⋅2𝑙−1 =𝛼𝑗 Hence, we observe that the operators 𝑈𝑖and 𝑈𝑗mark consecutive states. Therefore, given that operator 𝑈𝑖marks 2𝑖−1 states and it is only applied when 𝑏𝑖= 1, the number of states marked (which are consecutive) are: 𝑛 ∑ 𝑖=1 𝑏𝑖⋅2𝑖−1 It is clear that this is exactly 𝑚states (9). As these states are consecutive and the state |0⟩=|0 … 0⟩is marked, the oracle formed by all the operators described, 𝑉⋅(𝑛−2 ∏ 𝑖=0 𝑈𝑖)⋅𝑋⊗𝑀0(12) gives a 𝜋-phase to the first 𝑚states, which are the numbers smaller than 𝑚. We can conclude that operator (8) gives a 𝜋-phase to numbers smaller than 𝑚.□ The Journal of Systems & Software 219 (2025) 112203 5 J. Sanchez-Rivero et al. Fig. 2. Full circuit implementing operation less-than 42 with 6 qubits. 5. Results The best way to show the functionality of the less-than oracle implementation presented in this work is through simulations of different examples of the generated circuits and experiments on real quantum devices.5For this paper, we have used Qiskit (tA v et al.,2021) for generating the quantum circuits and running the experiments. For the algorithm to work as intended is needed to initialise all qubits to a uniform superposition of 0s and 1s by applying a Hadamard gate to each one. We show the results of amplifying the desired states as described by chapter 6 of Nielsen and Chuang (2000). To perform Amplitude Amplification, it is needed to initialise all qubits to a uniform superposition of 0s and 1s by applying a Hadamard gate to each one. Moreover, a diffusion operator is applied after the oracle. Depending on the fraction 𝑁∕𝑀(being 𝑀the number of desired states and 𝑁the total number of states), we need to repeat the pair oracle-diffuser several times, with a maximum of ⌈𝜋∕4√𝑁∕𝑀⌉times. In Fig. 2, we show an example of the full circuit implementing the operation less-than 42 with 6 qubits, including the initialisation with Hadamard gates, the two repetitions of the pair oracle-diffuser and the measure. All our results are generated by running the circuit several times, each of those runs is called shot. Each shot is the result provided by measuring after running the circuit. Hence, the output of one shot is just one state. Figures in this section represent the relative frequency (y-axis) of each state (x-axis) measured in the several shots realised. The results shown are generated by running 20,000 shots of each circuit. This choice is based on the maximum number of shots allowed in IBM real quantum devices. This is done to properly compare simulations and real experiments. 5.1. Simulations Simulations shown in this section were run on a standard laptop6 and execution time ranged between 8 and 10 s for each of them. Figs. 3 and 4are examples with 6-qubit circuits. Fig. 3 shows the result of the less-than 42 amplification. The desired state is a superposition of the first 42 states: 1 √42 41 ∑ 𝑖=0|𝑖⟩(13) The pair oracle-diffuser had to be repeated 2 times to reach maximum amplification of the desired state. Full circuit can be seen in 5The code for the automatic generation and the data of the simulations and experiments can be found in Code and Data. 6CPU: Intel(R) Core(TM) i5-7200U CPU @ 2.50 GHz, 2701 MHz. RAM: 8 GM. Fig. 2. It can be seen that the results are exactly as we would expect save for minor frequency differences. This is due to the number of shots simulated. The frequency of each number tends to the theoretical value (1∕42 in this case) when the number of shots tends to infinity. Fig. 4 displays results of the less-than 13 operation. In contrast with results in Fig. 3, in this case there are some small occurrences of nondesired states. The cause of this is that the best amplification possible, which occurs with 1 iteration, is not exactly 100%. Results from less-than 4 operation on a 4-qubit circuit are shown in Fig. 5. In this case, the number of iterations of the pair oracle-diffuser is also 1, however the amplification reaches 100% measurement probability of the desired states. The main objective of this example is to compare a simulation with an execution on a real quantum device. Such results are available in the next section. The numbers used to perform the less-than operations in this section (42, 13 and 4) have been chosen to showcase that Amplitude Amplification, even in absence of noise, does not always perfectly amplify the desired states. 5.2. Experiments on real quantum hardware We have run the last simulation, less-than 4 amplification on a 4qubit circuit, on a real quantum device with 20,000 shots as well. We have chosen this operation specifically because for 4 qubits the full amplification circuit is the one with lower depth. Results of the experiment can be seen in Fig. 6. The error is noticeable, which is an expected behaviour with real quantum hardware. Despite these errors, the desired states have a combined frequency of ≈63%, even though they are 4 states out of 16 in total, 25%. Hence we managed to amplify the measurement probability of the desired states by a ≈2.5factor on an actual quantum device. The results of the experiments with more than 4 qubits are indistinguishable from pure noise. The depth of the multi-controlled gates that affects all qubits in the circuit (for example, the multi-controlled Z-gate in the diffuser) scales heavily with the number of qubits and the fidelity of the device is not enough to achieve a satisfactory result. The device used for this experiment was an IBM machine, ibm_nairobi, on November 18th, 2022 13:22 UTC. This device uses a Falcon r5.11H processor. The calibration data of the device at the time of the experiment can be found in the repository in Code and Data. 6. Comparison with other methods In this section, we realise several comparisons with other methods, both in depth and type of gates. In a previous work from the authors (Sanchez-Rivero et al.,2023), an initial, less efficient version of the oracle generation algorithm presented here was compared with the Qiskit method UnitaryGate already showing better performance in terms of circuit depth. 6.1. Depth comparison with diagonal method Firstly, we show a comparison of the depth between our method, Less-Than, and the Diagonal method. In order to do so two different transpilers are used, the statevector transpiler of Qiskit, which assumes all the qubits are connected with each other, and the fake_ washington_v2,7a fake provider which has the same properties, namely the topology, as the real device Washington from IBM. From now on we will denote this provider just Fake Washington. In Fig. 7, we show the comparison using the statevector as a transpiler. The figure depicts the mean plus and minus the standard deviation (std) of the depth of both methods, Less-Than in blue circle and Diagonal in violet triangle. It can be observed that from 12 qubits 7https://qiskit.org/documentation/apidoc/providers_fake_provider.html. The Journal of Systems & Software 219 (2025) 112203 6 J. Sanchez-Rivero et al. Fig. 3. Simulation of less-than 42 amplification with 6 qubits and 20,000 shots. Fig. 4. Simulation of less-than 13 amplification with 6 qubits and 20,000 shots. Fig. 5. Simulation of less-than 4 amplification with 4 qubits and 20,000 shots. Fig. 6. Real experiment of less-than 4 amplification with 4 qubits and 20,000 shots. onwards the difference between the methods is more than 100%. Both the mean and std are computed using all the numbers for each number of qubits. For instance, with 𝑛= 6 qubits the depth is the mean of the implementations of the oracles Less-Than 1,2,…, and 26− 1 = 63. Hence, the mean and std for each number of qubits 𝑛is made with 2𝑛−1 implementations. Given the topology of the statevector transpiler, in which every pair of qubits is connected, for some values of 𝑚our method does The Journal of Systems & Software 219 (2025) 112203 7 J. Sanchez-Rivero et al. Fig. 7. Depth comparison between less-than and diagonal method using statevector as a transpiler. The 𝑦-axis represents the depth while the 𝑥-axis represents the number of qubits. (For interpretation of the references to colour in this figure legend, the reader is referred to the web version of this article.) Fig. 8. Depth comparison between less-than and diagonal method using fake_washington_v2 as the transpiler. The 𝑦-axis represents the depth while the 𝑥-axis represents the number of qubits. not outperform Diagonal. Still, on average, the depth of the circuit generated by our method is smaller and grows slower than the one generated by Diagonal. The complete dataset may be found in the repository in Code and Data. Fig. 8 shows the comparison using Fake Washington as a transpiler. The main difference we observe is that the depth is slightly larger than using the statevector transpiler. This is because of the topology of the device, so multi-controlled gates need more gates to be carried out. The difference between the methods is notable from 12 qubits onwards, as in the previous case. Moreover, and contrary to the previous case, from 12 qubits (included) onwards, our method outperforms Diagonal in terms of depth for every value of 𝑚. 6.2. Count gates comparison with diagonal method We conduct the same comparison as in the previous section however in this occasion with the number of gates. As two transpilers are used, two comparisons are shown. The gates used when using the statevector transpiler can be seen in Table 1 and depicted in Fig. 9. It can be noticed that we have reduced the gates to only 𝐶𝑋, two-qubit gates, and onequbit gates, denoted by 𝑈. Furthermore, the transpiling time in seconds has also been added to the comparison, which can be noticed in Fig. 10. We can observe that, even though Diagonal outperforms Less-Than in amount of time and gates for low number of qubits, from 8 qubits onwards, the transpiling time is smaller using Less-Than method. 𝐶𝑋 are fewer from 10 qubits onwards, with a linear growth against the exponential growth of the Diagonal method. With respect to the onequbit gates, we see an improvement from 12 qubits onwards, apart from the linear growth of the Less-Than method compared with the exponential one of Diagonal method. In Table 2 the same comparison is shown taking the Fake Washington as the transpiler. As in the previous case, the comparison can be also observed as a graph in Fig. 11. The results displayed are similar to the ones in the previous comparison, however all the figures are higher given the topology of the device. Time overperformance begins at 9 qubits, as the 𝐶𝑋 gate count. Regarding 𝑈gates, it represents the sum of gates 𝑅𝑍,𝑆and 𝑋, the one-qubit gates the Fake Washington transpiler uses. This number is lower in the Less-Than method from 11 qubits onwards. The disaggregated figures can be found in Table 3, also represented in Fig. 12. While our method is better in terms of gate count and depth, it should be noted that Diagonal method is designed to implement any oracle given the states to be phase-marked and our method is designed only for the Less-Than operation. The Journal of Systems & Software 219 (2025) 112203 8 J. Sanchez-Rivero et al. Fig. 9. Comparison of gate count between our method less-than, diagonal and phase tolerant using statevector as transpiler. Fig. 10. Comparison of transpiling time between our method less-than and diagonal using both transpilers. 6.3. Count gates comparison with Phase Tolerant (PT) synthesis The Phase Tolerant synthesis is presented in Seidel et al. (2023) as an automatic method for generating oracles for arbitrary data structures. The authors focus on gate count by type used in the quantum circuit instead of the circuit depth. The gate count metric is, as well as the circuit depth, a measure of the circuit’s complexity. It provides a deep understanding of the implementation, as well as giving a clear insight of the generated circuit. The same metric is used to conduct the complexity analysis of the Less-Than method and the comparisons are shown in Table 4. This comparison is also depicted in Fig. 9. With respect to the transpiler, they use the QASM Simulator from Qiskit, which assumes all qubits are connected to each other. Therefore, we conduct the comparison with our results using the statevector transpiler. It can be seen that the PT method requires double the amount of qubits for the same data size.8Moreover, the count of 𝐶𝑋 and 𝑈gates is larger 8This is the total number of quantum states which can be encoded in the non-ancilla qubits. In our case, the non-ancilla qubits are all the qubits in the circuit. The Journal of Systems & Software 219 (2025) 112203 9