Partial Equivalence Checking of Quantum Circuits
Authors:
- 1 September 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 594-604
Abstract
Equivalence checking of quantum circuits is an essential element in quantum program compilation, in which a quantum program can be synthesized into different quantum circuits that may vary in the number of qubits, initialization requirements, and output states. Verifying the equivalences among the implementation variants requires proper generality. Although different notions of quantum circuit equivalence have been defined, prior methods cannot check observational equivalence between two quantum circuits whose qubits are partially initialized, which is referred to as partial equivalence. In this work, we prove a necessary and sufficient condition for two circuits to be partially equivalent. Based on the condition, we devise algorithms for checking quantum circuits whose partial equivalence cannot be verified by prior approaches. Experiment results confirm the generality and demonstrate the efficiency and effectiveness of our method. Our result may unleash the optimization power of quantum program compilation to take more aggressive steps.Keywords
All Related Versions
Funding Information
- Ministry of Science and Technology
This publication has 33 references indexed in Scilit:
- Equivalence Checking in Multi-level Quantum Systems2014
- Verification of Concurrent Quantum Protocols by Equivalence Checking2014
- Quipper2013
- SAT-Based Model Checking without Unrolling2011
- An XQDD-Based Verification Method for Quantum CircuitsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008
- Towards a quantum programming languageMathematical Structures in Computer Science, 2004
- A Lambda Calculus for Quantum ComputationSIAM Journal on Computing, 2004
- Toward an architecture for quantum programmingThe European Physical Journal D, 2003
- Interpolation and SAT-Based Model Checking2003
- Sequential equivalence checking based on structural similaritiesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000