Verification of Quantum Circuits through Discrete-Time Barrier Certificates

Marco Lewis, Sadegh Soudjani, Paolo ZulianiarXiv 2024 · DOI · arXiv

Abstract

Quantum circuit verification is a critical yet complex task due to the high-dimensional, complex-valued nature of quantum states. This paper introduces an automated method for safety verification by treating quantum circuits as discrete-time dynamical systems. By leveraging Hermitian Sum of Squares (HSOS) optimization and $k$-induction, the authors develop a framework for generating barrier certificates directly in the complex domain. This approach avoids the computational penalties of real-valued translations and provides a robust mechanism for proving that a quantum system will never enter an unsafe state.

Introduction

As quantum computing matures, ensuring the correctness and safety of quantum circuits becomes paramount. Traditional verification methods, such as manual theorem proving or automated SMT solvers, often struggle with the continuous and complex-valued dynamics of quantum mechanics. A common workaround involves "flattening" complex variables into pairs of real numbers, which significantly increases the number of variables and slows down optimization solvers. This paper addresses these challenges by proposing a native complex-domain verification framework using discrete-time barrier certificates.

Methods

The proposed framework models a quantum circuit as a sequence of unitary transformations, where each gate application corresponds to a discrete time step in a dynamical system.

Discrete-time representation of a quantum circuit as a sequence of unitary gates $U_0, \dots, U_{k-1}$.

To handle the unitary (rotational) nature of quantum evolution, the authors introduce $k$-inductive barrier certificates. Standard barrier certificates require the system to move away from unsafe regions at every step, which is often too restrictive for oscillating quantum dynamics. $k$-induction relaxes this by requiring safety only after $k$ steps. The search for these certificates is automated using Hermitian Sum of Squares (HSOS) optimization, a complex-domain generalization of Sum of Squares (SOS) programming. This ensures that the resulting barrier function, $P(z, \bar{z})$, is real-valued and natively compatible with complex amplitudes.

Experimental Evaluation

The approach was evaluated on several fundamental quantum benchmarks, including repeated phase (Z) gates, bit-flip (X) gates, and Grover’s search algorithm.

Example of a benchmark quantum circuit structure used to evaluate the verification framework, showing a 3-qubit configuration.

The tool successfully generated safety certificates for 1-qubit and 2-qubit systems in a matter of seconds to minutes. The results confirmed that staying in the complex domain improves solver efficiency by avoiding the "variable doubling" penalty. However, the 3-qubit version of Grover’s algorithm highlighted scalability issues, as the number of terms in the barrier polynomial grows exponentially with the number of qubits ($2^n$).

Conclusion and Future Work

This work demonstrates the power of native complex-domain optimization for quantum verification. The $k$-inductive approach effectively captures the periodic nature of quantum gates. Future research will focus on addressing the "curse of dimensionality" through geometric representations of quantum states and extending the framework to model continuous-time systems and stochastic noise.

Summary updated

Abstract

Current methods for verifying quantum computers are predominately based on interactive or automatic theorem provers. Considering that quantum computers are dynamical in nature, this paper employs and extends the concepts from the verification of dynamical systems to verify properties of quantum circuits. Our main contribution is to propose k-inductive barrier certificates over complex variables and show how to compute them using Hermitian Sum of Squares optimization. We apply this new technique to verify properties of different quantum circuits.
BibTeX
@misc{lewis2024verification,
  author = {Marco Lewis and Sadegh Soudjani and Paolo Zuliani},
  title = {{Verification of Quantum Circuits through Discrete-Time Barrier Certificates}},
  year = {2024},
  eprint = {2408.07591},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.07591},
}
Figure