CS Paper Radar

Controlled PROP: Theory and Applications to Quantum Circuits

Noé Delorme, Simon Perdrix

cs.LO quant-ph ·submitted 2026-10-16 09:30 UTC · v1

Abstract

Control is a fundamental concept in quantum and reversible computational models. It enables the conditional application of a transformation to a system, depending on the state of another system. We introduce a general framework for diagrammatic reasoning featuring control as a constructor. To this end, we provide an elementary axiomatization of control functors, extending the standard formalism of PROPs to controlled PROPs. As an application, we show that controlled PROPs facilitate diagrammatic reasoning for quantum circuits. In particular, they admit a simple and complete axiomatization involving at most three qubits, whereas in the standard PROP setting, completeness necessarily requires axioms involving arbitrarily many qubits.

Closest papers

Nearest neighbours by meaning across the whole index.

A Complete Equational Theory for Quantum Circuits with Generalized Control

cs.LO math.CT ·2026-11-04 ·William Schober, Scott Wesley
published similarity 0.75
Abstract · In Proceedings QPL 2026, arXiv:2611.04069

Controlled subcircuits are commonplace in quantum algorithms as they represent the quantum analogue of branching statements (if then). We introduce a generalization of controlled subcircuits in the form of a binary operation which sends pairs of unitary quantum circuits to a generalized controlled operation, whose semantics are based on matrix exponentials and logarithms. The family of quantum circuits with generalized controlled operations and circuit exponentiation is denoted HQC for Hierarchical Quantum Circuits. We formalize HQC as a modified prop category using a novel category-theoretic construction, and provide a sound and complete equational theory for diagrammatic reasoning in HQC.

0.37

Granthi: Higher-Order Quantum Programming via Unitary Wiring

cs.ET quant-phcs.LOcs.PL ·2026-08-20 ·Samson Abramsky, Radha Jagadeesan
publishedcode/data similarity 0.60
Abstract · OOPSLA 2026. v3. New version with a corrigendum (fixing a soundness error in the typing of sums), and revised proofs of an expanded formal t…

Many mainstream quantum programming languages confine higher-order structure to a classical host while restricting the quantum layer to first-order operations on qubits. This paper presents Granthi, a purely unitary higher-order quantum programming language built on three design commitments: quantum programs are first-class values that may be passed, returned, and coherently composed; additive structure is tag-preserving routing rather than observational branching, so control may remain in superposition; and programmer-facing finite label types with staged reversible-operation bindings provide domain-level control spaces without exposing tag management. These bindings are eliminated by elaboration before Source typing. Granthi deterministically normalizes each Source program to a canonical wiring form. Every well-typed Source program, including a term of function type, has a unitary boundary interpretation. Under backend correctness (BC), the reference compiler produces a unitary circuit realizing that interpretation. Granthi's currently supported executable fragment is implemented end-to-end: an OCaml DSL elaborates surface programs through a higher-order Core IR to executable quantum circuits via pytket. The language directly supports the pure-unitary quantum switch for explicitly supplied operations; closed instances compile to static circuits. It also supports interference on control-flow history and structured finite control, all within the purely unitary fragment

0.37

Staged Hybrid Quantum-Classical Programming

cs.PL cs.LO ·2026-09-06 ·Chuta Sano, Peng Fu, Ryan Kavanagh, Jennifer Paykin, Brigitte Pientka
theory similarity 0.59
Abstract

Hybrid quantum-classical computing systems consist of a classical control system that sends quantum circuits and receives measurement results from a quantum co-processor. Such systems allow us to model algorithms that require the classical control system to generate quantum circuits on the fly, potentially based on prior measurement results. This is challenging, as the classical control system must generate quantum circuits that manipulate live quantum states. In this setting, the classical control system is generating further quantum circuits while the quantum co-processor is internally maintaining the state of the live qubits; this is not ideal, since this not only is costly but also introduces additional sources of noise to the live qubits. Thus, we want to minimize the latency between receiving measurement results and sending the next quantum circuit to be executed by pre-computing quantum circuits. We introduce HyQ (pronounced haiku), a multi-modal language based on adjoint logic that pre-generates quantum circuits before executing a hybrid quantum-classical program. We achieve this by separating our semantics into two distinct stages: 1) compile-time generation of quantum circuits and classical runtime code and 2) execution of the classical runtime code that instruments the quantum co-processor. This separation between stages allows us to formally guarantee that all circuit-generation logic occurs before the instrumentation logic, i.e., the actual runtime, and minimizes the idling of the quantum co-processor at runtime. We give a type system, a circuit-normalization semantics for the compile-time stage, which eagerly performs all circuit-generation logic, and a runtime semantics for HyQ that corresponds to the second stage. We prove type preservation and progress for both semantics.

0.18

QEDIA: Quantum Program Verification in Lean

cs.PL quant-ph ·2026-10-13 ·Yuanjie, Ren, Zhicheng Zhang, Junyi Liu, Jinzheng Li +2 more
highly cited similarity 0.59
Abstract

Practical quantum programs interleave quantum and classical computation: classical data shape the quantum operations that are performed, and measurement outcomes shape the classical computation that follows. Formal verification of such programs in a proof assistant requires mechanizing a program logic that handles this interplay consistently at every level, from the mathematics of quantum mechanics, through program syntax and semantics, to specifications and proof rules. Such mechanizations, along with the program proofs built on them, typically require substantial manual effort. We present QEDIA, a framework for verifying quantum programs with classical variables in Lean 4. At its foundation is an open library that formalizes the quantum Hoare logic QHL+ across all these levels and proves the logic sound for both partial and total correctness. We construct the library and the program proofs, under human supervision, using an LLM-based prover agent, whose general-purpose core we extend for quantum program verification. We illustrate QEDIA with verified programs including the quantum Fourier transform, phase estimation, repeat-until-success circuits, and Hamiltonian simulation.

0.29

Computons for Control-Driven Boolean Circuits

cs.LO ·2026-11-01 ·Damian Arellanes
similarity 0.58
Abstract · Extended version of the paper "Compositional Control-Driven Boolean Circuits". DOI: 10.1007/978-3-032-22469-9_2

Boolean circuits abstract away from hardware aspects to capture the logical structure and computational behaviour of digital components. Despite their long history of study, their compositional foundations have received comparatively little attention. Building on the theoretical foundations of computons introduced in previous work, we develop a concrete and operationally defined model of high-level computation for control-driven Boolean circuits. We describe colimit-based operators for composing such circuits into sequential, parallel, branching and iterative structures, supported by concrete operational semantics grounded in abstract computing devices. The framework refines the semantics of composition, establishes the algebraic properties of its operators and introduces atomic circuits to support more expressive computation units. We demonstrate the applicability of the proposed framework through examples from propositional logic, biomedicine and electronics, and establish an operational equivalence with respect to classical Boolean circuits through a systematic transformation that accommodates gates of arbitrary arity. By this equivalence, we show that control-driven Boolean circuits are at least as powerful as their classical counterpart. That is, they are capable of non-uniformly computing any Boolean function over inputs of arbitrary length. Implementations in Idris and Java validate the practical realisability of the framework.

0.21

Synthesis of Compact and Expressive Quantum-Circuit Optimizations

cs.PL ·2026-09-01 ·Wei Qiang, Ronghui Gu
publishedhot direction similarity 0.58
Abstract · To appear in Proc. ACM Program. Lang. 10, OOPSLA2 (2026)

Today's quantum devices are noisy, so reducing circuit size is critical for reliable execution. Existing rule-based optimizers often rely on large rule sets that are difficult to manage and still miss long-distance transformations. We present QSymb, a framework for synthesizing compact and expressive quantum-circuit rewrite rules with formal guarantees. We formalize symbolic rewrite rules in which a symbolic gate represents infinitely many subcircuits. We then define canonical symbolic rules of the form $L;S = S;R$ and prove that they constitute a compact generative core from which general symbolic rules can be derived. On top of this formal foundation, given a gate set, QSymb synthesizes (1) a small, non-derivable concrete rule set that is complete up to chosen size and qubit bounds, and (2) a small but expressive canonical symbolic rule set that captures transformations beyond finite or monomial-only patterns. We further present rule anchoring to derive optimization-effective rules from canonical symbolic rules. Together, these results provide both expressiveness and guarantees: soundness of synthesized rules via validation, non-derivability, and bounded completeness. On the IBM-Eagle gate set, QSymb strictly outperforms state-of-the-art rewrite-based optimizers (Qiskit, Guoq, Quartz, TKET, and Queso) in two-qubit-gate reduction on 90%, 67%, 82%, 85%, and 83% of standard quantum algorithm benchmarks, respectively; on Nam gate set, the corresponding rates are 88%, 74%, 81%, 86%, and 82.9%. It achieves final average two-qubit-gate reductions of 27.44% and 29.95%, respectively.

0.41

QILP-0: Constructing Observational Declarative Twins of Quantum Circuits

cs.AI quant-ph ·2026-09-01 ·Marina de la Cruz Echeandía, César Luis Alonso, Tony Ribeiro, Alfonso Ortega de la Puente
hot direction similarity 0.56
Abstract · 39 pages, 7 figures. Submitted to Knowledge-Based Systems

This paper introduces QXymb, a general framework for constructing observational declarative twins of quantum circuits, and develops QILP-0, its first complete order-0 specialization. QILP-0 constructs a finite multi-valued propositional logic program from observed circuit behaviour within a declared observational scope. The pipeline traverses a declared family of quantum observables incrementally according to a reproducible structural grading and a declared observational reference horizon. Progress is quantified through reference-relative coverage against a fixed target-independent reference. Observable responses are organized through target-independent geometry, while retained latent structure is mapped deterministically back to original observable columns before symbolic processing, preserving observational semantics and provenance. Selected observable profiles are converted into a finite relation through admissible target-independent discretization. The target is used only afterwards to audit twin-admissibility and induce the declarative theory. A theory is certified as an exact observational declarative twin when it completely and correctly reconstructs the resulting finite task-conditioned discrete relation. Logical exactness is therefore separated from numerical, backend, provider, and discretization uncertainty, which is retained as audit metadata. Validation uses two complementary QML settings. Exhaustive Bars & Stripes experiments compare product and grid-CZ embeddings from 16 to 100 qubits and exercise the native-discrete branch. Low-Depth MNIST analyses all 14,708 digit-0/1 instances before and after a trained variational quantum transformation and exercises continuous discretization. In every reported relation, the induced QILP-0 theory achieves complete, conflict-free reconstruction with strict accuracy equal to one.

0.42

Reasoning about Shared-Qubit Concurrency in Quantum Computing

cs.DC quant-phcs.LOcs.PL ·2026-11-03 ·Mingsheng Ying
similarity 0.56
Abstract

In this paper, we develop a semantic model for the parallel execution of quantum circuits, providing a formal foundation for studying shared-qubit concurrency in quantum computing. As in classical shared-memory concurrency, parallel quantum circuits may interfere with one another through operations on shared qubits. However, quantum entanglement and the noncommutativity of quantum operations introduce additional challenges for reasoning about their correctness. To address these challenges, we generalise the classical Owicki-Gries method to quantum computing at the level of quantum circuits. Our approach enables compositional reasoning about parallel quantum circuits by separating the verification of individual components from the analysis of interference between them. We formulate proof rules for establishing the correctness of parallel quantum circuits and prove their soundness with respect to the proposed semantic model.

0.30