A Quantum Algorithm for System Specifications Verification

Abstract

Verifying system specifications is a crucial requirement in science and technology, as it improves accuracy and efficiency in systems engineering. However, traditional computers are time-consuming and cannot efficiently check the consistency of system specifications for classical and quantum systems due to exponential complexity costs. Currently, there is no quantum approach available for verifying consistency in quantum systems. This paper introduces a novel quantum algorithm that utilizes the entanglement measure to efficiently check the consistency of unknown system specifications represented by m oracles. The proposed algorithm has a time complexity of O(m-2), which is independent of the input size n and depends only on a predetermined error margin, providing exponential speedup compared to the classical approach with a time complexity of O(m2n). Moreover, the proposed algorithm can handle weighted superposition input states, which are impossible for classical computers to handle. Thus, the algorithm has the potential to check the consistency of both quantum and classical system specifications. The proposed algorithm is realized experimentally using IBM’s Aer simulator with an input size of n=12. The experimental results closely aligned with the theoretical predictions, demonstrating the algorithm’s efficiency in checking the consistency of system specifications. Specifically, the proposed algorithm achieved a quantum supremacy ratio of 300% to 3100% compared to the classical algorithm, highlighting its significant advantage in terms of time complexity. Additionally, the simulation results confirmed the efficiency of the proposed algorithm in checking the consistency of the quantum system’s specifications.