Rapid solution of logical equivalence problems by quantum computation algorithm

Mohammed Zidan

doi:10.1016/j.asoc.2022.109844

2023-01-01

PRE

DOI：10.1016/j.asoc.2022.109844

原文链接

原文求助

摘要

En 中文

We present a quantum computation algorithm that enables solving the problem of logical equivalence verification in exponentially less time than the classical deterministic computation. In this novel quantum algorithm, the oracles of the two evaluated functions are executed in series to yield a common target qubit which then interacts with an ancillary qubit. We found that the degree of entanglement (measured by the concurrence) of the target and ancillary qubits is a reliable witness for the logical equivalence property of the two functions. The steps number of the quantum algorithm is inversely proportional to the square of the standard error epsilon 2 of the measured concurrence value, with no dependence on the input size ' n ' of each function. This corresponds to a number of evaluations of the two functions: O(epsilon-2) for the quantum algorithm compared with O(2n) for the classical approach. To assess the algorithm performance, two sets of experiments are conducted using the IBM Q Experience simulator for input sizes: 2 and 12 variables per function. While the former verifies that the results of the experiment are in a good match with the theory, the latter showcases the quantum supremacy of the presented algorithm. In particular, The latter shows that the quantum algorithm requires only 200 oracles queries compared with 213 queries for the classical algorithm. (c) 2022 Elsevier B.V. All rights reserved.

Keyword:

Quantum computing

Quantum algorithms

Logical equivalence

Quantum verification