Using Quantum Computers to Speed Up Dynamic Testing of Software

It is theoretically possible to convert any CC program into a QC program (because QC implements a quantum Turing machine [7, 3]), but there are limitations and practical considerations (see Section 4). Essentially, a classical algorithm is converted into reversible circuits [20], which are then converted into quantum circuits [9]. These conversions can be done automatically.

Several nascent tools for converting classical to quantum circuits already exist. Qiskit, for example, allows compiling a classical function to a quantum circuit transparently (by adding the decorator @classical_function). Qiskit converts classical circuits to quantum circuits using the Tweedledum library [28]. Currently, the compilation is limited to binary inputs/outputs and logical operators (see Section 3.1.1 for an example). Another example is the staq toolkit, which can convert classical Verilog circuits to a quantum assembly language (QASM) [6]. Finally, StaffCC compiler [18] extension RKQC [16] is also capable of compiling classical circuits to QASM (including integer addition and multiplication operations [34]).

Hopefully, the abovementioned tools will evolve in the future to enable the conversion of any classical program.

Section 2.1 discussed the possibility of interpreting input $x$ into $f$ as a bit string. Furthermore, bit strings can represent arbitrary complex data structures. Thus, to convert $\vec{z}$ into $x$, we must convert $\vec{z}$ into a bit string.

For example, imagine that $\vec{z}$ has two elements: an integer $z_{1}$ and a 3-character string $z_{2}$, i.e., $g(\vec{z})=g(z_{1},z_{2})$. Furthermore, suppose that storing an integer and a string character requires $64$ and $8$ bits, respectively. We will need $88=64+3\times 8$ bits to represent the input, i.e., $N=2^{88}$.

Software programs may produce any output (or no output at all), whereas $f(x)$ should return either zero or one. We can satisfy this requirement by wrapping³³3We can also leverage try-catch blocks in high-level programming languages. $g(\vec{z})$ in code that returns an exit code of $0$ on success and $1$ on error (similar to operating system exit status codes).

Suppose we implement a function $g(z_{1},z_{2})$, where $z_{1}$ is a 2-bit integer and $z_{2}$ is a boolean variable. The next step is to test our implementation of $g(z_{1},z_{2})$.

Suppose we inject two defects, e.g., $g(z_{1},z_{2})$ returns incorrect results when $z_{1}=3$ and $z_{2}=\textrm{false}$ or when $z_{1}=2$ and $z_{2}=\textrm{true}$. Algorithm 3 gives a trivial example of such code. Code review of Algorithm 3 immediately reveals the problem. Of course, in real-world scenarios, we would not know these values of $\vec{z}$ upfront; this simplification is for demonstration purposes only.

Step 2 of Algorithm 2 converts $g(z_{1},z_{2})$ into $f(x)$. As $z_{1}$ and $z_{2}$ can be represented by 3-bit strings, $N=2^{3}=8$. The first two bits of the bit string store an integer $z_{1}$, while the last bit stores a boolean variable $z_{2}$.

We will implement our example using Qiskit; code listing can be found on Zenodo [21].

As was described in Section 2.3, converters from a classical to a quantum circuit are still in their infancy, and Qiskit operates only on binary variables. Thus, we must manually reduce the code in Algorithm 3 to the format understood by Qiskit (eventually, converters and compilers will do this automatically). Listing 1 shows the result of the conversion to $f(x)$. Once in this form, Qiskit’s @classical_function decorator automatically converts $f(x)$ to the quantum circuit (so-called bit-flip oracle [25]) shown in Figure 3.

Using Grover’s algorithm requires a phase-flip oracle [25]. Bit-flip oracles are converted to phase-flip oracles by placing their return values between NOT and Hadamard gates as shown in Listing 2. The phase-flip oracle circuit, which we pass to the search algorithm, is shown in Figure 4.

In Step 2 of Algorithm 2, we pass the oracle’s circuit to the quantum counting algorithm⁴⁴4Qiskit’s implementation of the quantum counting algorithm [11] is illustrated in [5, Sec. 3.9]., which returns $K$, the number of inputs causing defects. In our case, $K=2$. As $K\neq 0$ and $K\neq N$, we go to Step 2.

Step 2 of Algorithm 2 involves passing oracle’s circuit to Grover’s algorithm to find specific input values that cause failures. Using the $K$ value from Step 2, we can calculate the number of iterations of Grovers’ algorithm: $r(N,K)=r(8,2)=2$.

Execution is performed on the Qiskit v.0.37.0 Aer simulator v.0.10.4 (providing an ideal noise-free QC) as well as on the IBM Quantum r4T Processor v.1.0.38 with five qubits, namely, ibmq_lima [2]. With ibmq_lima, we compare the output based on Qiskit’s simulator of ibmq_lima as well as the output from the actual QC.

The output of Grover’s algorithm can be seen in Figure 5. According to the simulators and the real QC, 110 and 101 are the top-two returned values of $\omega$. However, due to noise, the $p$-values on the real QC are lower than those on the simulators.

Step 2 of Algorithm 2 converts $\omega$ back to $\vec{z}$ values:

These are the values we expected. In other words, Algorithm 2 correctly identified two inputs that caused errors in software under test.

How laborious is Algorithm 2?

In Step 2, code written in a high-level language (e.g., C/C++ or Python) is compiled into a quantum circuit. Depending on the compiler, the complexity of this process may vary, but compiler designers are aiming for $O(\alpha^{2})$, where $\alpha$ is the size of the input [13]. In practice, even for large code bases with millions of lines of code, compilation on modern CC is relatively fast.

The computation complexity of Steps 2 and 2 is $O(\varepsilon^{-1}\sqrt{N/K})$ and $O(\sqrt{N/K})$, respectively [10, 11]. Complexity of Step 2 is proportional to the number of bits required to represent $x$, i.e., $O(\log_{2}{N})$. Therefore, we estimate that the majority of time will be spent on Steps 2 and 2, with the dominant term $O(\varepsilon^{-1}\sqrt{N/K})$.

When comparing exhaustive testing on CC and QC, QC is faster because exhaustive search on a CC requires $O(N)=O(2^{n})$ computations, while on a QC — only $O(\varepsilon^{-1}\sqrt{N/K})=O(\varepsilon^{-1}2^{n/2}K^{-1/2})$ computations.

$2^{n/2}$ grows much slower⁵⁵5For example, suppose $n=64$ bits. Then $2^{n}=2^{64}\approx 2\times 10^{19}$, while $2^{n/2}=2^{32}\approx 4\times 10^{9}$. than $2^{n}$, but it still increases exponentially. Thus, if our software has input parameters requiring many bits, the search will become prohibitively expensive, even on a QC. Therefore, let us explore non-exhaustive testing methods.

Let us consider the function $g(z_{3})$, where $z_{3}$ is a $64$-bit integer, i.e., $n=64$). There are only three input values we want to test, e.g., $z_{3}=\{7,200,1005\}$.

We will refer to the number of inputs in a subset as $N_{s}$. In our example $N_{s}=3$. To represent the input, we only need $\lceil\log_{2}{N_{s}}\rceil=\lceil\log_{2}{3}\rceil=2$ qubits rather than $64$ qubits. During compilation, we would add a data structure that mapped each of these three values to their 64-bit representations (note that we will still need $64$ auxiliary qubits to build oracle’s circuit, but we will only be measuring the two input qubits).

We will get $O(\varepsilon^{-1}\sqrt{N_{s}/K})=O(\varepsilon^{-1}2^{n_{s}/2}K^{-1/2})$ computations, where $N_{s}=2^{n_{s}}$, if we apply the complexity analysis logic discussed in Section 3.1.2. Therefore, as long as $N\gg N_{s}$, the non-exhaustive test will be significantly faster than the exhaustive test. Moreover, non-exhaustive testing on a CC would require $O(N_{s})=O(2^{n_{s}})$ computations, so QC will outperform CC.

As we need to add the code to map $\vec{z}$ to $x$, the cost of executing the oracle increases compared to the exhaustive testing case. Nevertheless, such look-up tables can be constructed efficiently; e.g., a hash table’s search complexity is $O(1)$. As a result, the computation time increase will be minimal.