Curator's Take
AI Commentary
This work tackles a long‑standing blind spot in quantum compilation by providing the first systematic method for certifying that a target unitary is incompatible with a prescribed hardware architecture, rather than merely trying to construct a circuit that approximates it. By casting the problem as a semidefinite program—and reducing Clifford cases to linear programming—the authors deliver practical, quantitative lower bounds on gate count or depth that can be used both in software optimisers and as experimental benchmarks of device capability. The approach complements existing synthesis tools, giving developers a rigorous way to rule out infeasible designs before costly hardware trials.
— Mark Eatherly
Summary
Determining whether a target unitary can be implemented within a prescribed quantum circuit architecture is a fundamental problem in quantum information, with direct implications for optimisation and compilation of quantum circuits, and hardware-efficient quantum computation. While existing synthesis and compilation methods are primarily constructive, they generally do not provide rigorous certificates that a unitary cannot be realised using given implementation resources. Here we introduce a general framework to define quantum circuit architecture witnesses, which certify the incompatibility of a unitary transformation with a specified quantum circuit architecture. We formulate the witness construction as a semidefinite program by maximising the fidelity between the Choi state of the target unitary and those of tested circuits. The resulting witnesses provide practical and quantitative certificates of incompatibility, implying lower bounds on implementation resources such as the gate count or circuit depth, and can also be used experimentally to benchmark quantum devices by certifying that an implemented unitary channel goes beyond the capabilities of a given circuit architecture. For Clifford unitaries, we exploit the stabiliser formalism to reduce the construction to linear programming, enabling both more efficient numerical certification for circuits containing on the order of seven two-qubit gates, and analytical witnesses for some families of architectures made of an arbitrary number of gates.