We show how to translate a subset of RISC-V machine code compiled from a subset of C to quadratic unconstrained binary optimization (QUBO) models that can be solved by a quantum annealing machine: given a bound $n$, there is input $I$ to a program $P$ such that $P$ runs into a given program state $E$ executing no more than $n$ machine instructions if and only if the QUBO model of $P$ for $n$ evaluates to 0 on $I$. Thus, with more qubits on the machine than variables in the QUBO model, quantum annealing the model reaches 0 (ground) energy in constant time with high probability on some input $I$ that is part of the ground state if and only if $P$ runs into $E$ on $I$ executing no more than $n$ instructions. Translation takes $\mathcal{O}(n^2)$ time effectively turning a quantum annealer into a polynomial-time symbolic execution engine and bounded model checker, eliminating their path and state explosion problems. Here, we take advantage of the fact that any machine instruction may only increase the size of the program state by a constant amount of bits. Translation time comes down from $\mathcal{O}(n^2)$ to $\mathcal{O}(n\cdot|P|)$ if memory consumption of $P$ is bounded by a constant, establishing a linear (quadratic) upper bound on quantum space, in number of qubits on a quantum annealer, in terms of algorithmic time (space) in classical computing. Our prototypical open-source toolchain translates machine code that runs on real RISC-V hardware to models that can be solved by real quantum annealing hardware, as shown in our experiments.
翻译:我们展示如何将从C子集中编集的RISC-V机器代码子集从C 子集中译为可使用量子反射机器解析的二次优化(QUBO) 模型中比QUBO 模型中变量多的Qubits 。 给一个程序,如果并且只有在QUBO模式中以美元计为美元执行不超过美元机器指令时,我们才能将它转换成零美元。因此,如果在QUBO 模型中,机器上比变量多的不限制的二进制优化(QUBO) 模型中,将模型的内值调整成0(地面),某些输入的美元有很高的概率(I美元) 美元是地面状态的一部分,只有美元运行到美元, 美元执行不超过美元的指示。翻译需要$ mathc{O} (n2) 时间将一个量的量子值转换成一个多数字, 在Q_BO 的模型中, 直线性运算算算中, 一个不断的量的量数数的量数数数值只能通过不断的量数的值程序。