论文标题
使用量子计算机加快软件的动态测试
Using Quantum Computers to Speed Up Dynamic Testing of Software
论文作者
论文摘要
在执行时，可以动态分析正在测试的软件以查找缺陷。但是，随着输入参数的数量和可能值增加，动态测试的成本上升。 本文研究了量子计算机（QCS）是否可以帮助加快为古典计算机（CCS）编写的程序的动态测试。为此，设计了一种方法，涉及以下三个步骤：（1）将经典程序转换为量子程序； （2）使用量子计数算法计算导致错误的输入数量，用$ k $表示； （3）使用Grover的搜索算法获得这些输入的实际值。 这种方法可以加速详尽而无尽的动态测试技术。在CC上，这些技术的计算复杂性为$ O（n）$，其中$ n $代表输入参数值的组合计数，传递给了测试的软件。相反，在QC上，复杂性为$ O（\ varepsilon^{ - 1} \ sqrt {n/k}）$，其中$ \ varepsilon $是测量$ k $的相对错误。 本文说明了如何应用该方法并讨论其局限性。此外，它提供了一个在模拟器和实际QC上执行的玩具示例。本文可能对学者和从业人员感兴趣，因为本文提出的方法可能是探索QC用于动态测试CC代码的起点。
Software under test can be analyzed dynamically, while it is being executed, to find defects. However, as the number and possible values of input parameters increase, the cost of dynamic testing rises. This paper examines whether quantum computers (QCs) can help speed up the dynamic testing of programs written for classical computers (CCs). To accomplish this, an approach is devised involving the following three steps: (1) converting a classical program to a quantum program; (2) computing the number of inputs causing errors, denoted by $K$, using a quantum counting algorithm; and (3) obtaining the actual values of these inputs using Grover's search algorithm. This approach can accelerate exhaustive and non-exhaustive dynamic testing techniques. On the CC, the computational complexity of these techniques is $O(N)$, where $N$ represents the count of combinations of input parameter values passed to the software under test. In contrast, on the QC, the complexity is $O(\varepsilon^{-1} \sqrt{N/K})$, where $\varepsilon$ is a relative error of measuring $K$. The paper illustrates how the approach can be applied and discusses its limitations. Moreover, it provides a toy example executed on a simulator and an actual QC. This paper may be of interest to academics and practitioners as the approach presented in the paper may serve as a starting point for exploring the use of QC for dynamic testing of CC code.
