Verification of Quantum Systems using Barrier Certificates

Marco Lewis, Paolo Zuliani, Sadegh Soudjani

Introduction

Quantum computing promises a paradigm shift in computational power, yet the physical systems that realize this potential are notoriously fragile. Environmental noise and the inherent difficulty of precise state preparation mean that we rarely know the exact initial state of a quantum system. This uncertainty presents a significant hurdle for formal verification: how can we mathematically guarantee that a quantum program or hardware component will remain within safe operational bounds throughout its evolution?

While classical formal methods like model checking and abstract interpretation have been adapted for quantum systems, they often struggle with the continuous, complex-valued nature of quantum mechanics. In classical control engineering, "barrier certificates" are a standard tool used to define a mathematical boundary that a system's trajectory can never cross. However, these certificates were originally designed for real-valued systems ($ \mathbb{R}^n $). Because quantum states exist in complex Hilbert spaces ($ \mathbb{C}^n $), a significant theoretical gap has existed in the verification toolkit. This paper bridges that gap by extending barrier certificates into the complex domain.

Methodology: Complex-Valued Barrier Certificates

The authors introduce a framework for Complex-valued Barrier Certificates that preserves the natural structure of quantum mechanics while providing rigorous safety guarantees.

1. Complex Extension and Conjugate-Flattening

Rather than decomposing complex numbers into their real and imaginary components—a process that doubles the number of variables and obscures the underlying physics—the researchers define barrier functions directly on complex variables. They utilize "conjugate-flattening" holomorphic functions. These functions take complex inputs but are structured to ensure the output is always a real value, allowing for the definition of a clear "safe" vs. "unsafe" threshold.

2. Automated Generation via Linear Programming (LP)

Manually identifying a barrier function for a specific system is mathematically intensive. To automate this, the authors employ a "template" approach using $k$-degree polynomials. By defining the requirements of a barrier certificate as a set of constraints, the search for a valid function becomes an optimization problem.

3. The Periodicity Shortcut

In many classical applications, finding barrier certificates requires Sum of Squares (SOS) optimization, which relies on Semidefinite Programming (SDP). While powerful, SDP is computationally expensive. The authors identify a unique characteristic of many quantum systems: they are periodic. By requiring the derivative of the barrier function to be zero ($ \frac{dB}{dt} = 0 $), they transform the verification task into a Linear Programming (LP) problem. LP solvers are significantly more mature and faster than SDP solvers, allowing for more efficient verification of quantum gates.

Experimental Validation

The proposed method was evaluated on three fundamental benchmarks of quantum computing, using the Schrödinger equation to model the continuous evolution of the states:

  • The Hadamard Gate: The researchers proved that a qubit undergoing a Hadamard transformation—essential for creating superposition—stays within safe bounds even when the initial state is "noisy" (e.g., a state slightly offset from the pure $|0\rangle$ state).
  • The Phase Gate: The method successfully verified the safety of phase-shifting operations.
  • The Controlled-NOT (CNOT) Gate: As a two-qubit gate essential for entanglement, the CNOT gate is more complex to verify. The authors demonstrated that if the control qubit starts near $|0\rangle$, the system is guaranteed to avoid states where the target qubit is flipped, effectively verifying the gate's conditional logic under initial uncertainty.

Visualizations using the Bloch sphere representation confirm these results, showing the calculated barrier as a plane that separates the evolving quantum state from designated "unsafe" regions.

Key Insights and Implications

  • Preserving Natural Structure: By staying in the complex domain, the analysis remains computationally leaner and more intuitive than "real-valued" translations of quantum states.
  • Safety as Geometry: The barrier certificate acts as a geometric "shield" in the system's state space. If a function is negative at the start and its value never increases, any region where the function is positive is mathematically unreachable, providing a rigorous guarantee of safety.
  • Scalability Potential: The move from SOS to Linear Programming is a major practical victory. Because LP can handle much larger problem sets, this approach may eventually be applicable to more complex quantum circuits.

Limitations and Future Work

Despite its success, the current approach faces several challenges. First, the LP-based method assumes a time-independent Hamiltonian (where the system's energy or logic does not change during the evolution). Extending this to time-dependent systems is necessary for verifying multi-step algorithms. Second, while LP is efficient, the state space of quantum systems grows exponentially with the number of qubits, making the verification of large-scale (e.g., 50-qubit) systems a daunting task. The authors suggest "Trotterization"—breaking large Hamiltonians into smaller, manageable pieces—as a potential path forward.

Finally, the paper focuses on continuous evolution, whereas most quantum programming is discrete and gate-based. Reconciling these two perspectives will be vital for integrating barrier certificates into the standard quantum software development lifecycle.

Summary updated

Abstract

Various techniques have been used in recent years for verifying quantum computers, that is, for determining whether a quantum computer/system satisfies a given formal specification of correctness. Barrier certificates are a recent novel concept developed for verifying properties of dynamical systems. In this article, we investigate the usage of barrier certificates as a means for verifying behaviours of quantum systems. To do this, we extend the notion of barrier certificates from real to complex variables. We then develop a computational technique based on linear programming to automatically generate polynomial barrier certificates with complex variables taking real values. Finally, we apply our technique to several simple quantum systems to demonstrate their usage.
BibTeX
@inproceedings{lewis2023verification,
  author = {Marco Lewis and Paolo Zuliani and Sadegh Soudjani},
  title = {{Verification of Quantum Systems using Barrier Certificates}},
  booktitle = {QEST},
  year = {2023},
  url = {https://openreview.net/forum?id=WVC2SGnPll},
}
Figure