CS Paper Radar

Essential Unitarity for Higher-Order Quantum Computation (Extended Abstract)

Samson Abramsky, Radha Jagadeesan

cs.LO ·submitted 2026-11-04 08:22 UTC · v1
published

Abstract

We develop a boundary-centric semantic framework for higher-order quantum computation, building on the Kelly-Laplaza description of compact closure and Abramsky's execution account. In the semantic carrier Perm(C), morphisms are complex-linear combinations of polarized boundary linkings, composed by execution. Finite-family addresses provide coherent control over finite-level quantum registers (qudits) while retaining the multiplicative boundary structure. We identify essential unitarity, a boundary condition extending ordinary unitarity to higher-order interfaces. On positive qudit registers it coincides with ordinary matrix unitarity; at higher order it expresses preservation of information across the full polarized boundary. We define a unit-free coherent quantum core generated bymultiplicative wiring, unitary gates on positive qudit registers, and contextual coherent control, and prove that every one of its morphisms is essentially unitary. The framework realizes an applied coherent quantum switch and the unitary stages of equal-ratio one-slot supermap dilations with explicit memory. Complete proofs appear in the full version of this paper.

Comment
In Proceedings QPL 2026, arXiv:2611.04069
Journal ref
EPTCS 456, 2026, pp. 1-17
DOI
10.4204/EPTCS.456.1

Closest papers

Nearest neighbours by meaning across the whole index.

Intuitionistic Unitary Linear Logic: A Proof-Theoretical Approach to Purely Quantum Higher-Order

cs.LO ·2026-09-02 ·Julien Lamiroy, Benoît Valiron, Renaud Vilmart
theory similarity 0.63
Abstract · 15 pages, submitted to CSL 2027

Although the circuit model for quantum computation is well established, it is incapable of representing non-causal higher-order quantum processes such as the quantum switch. If several models of non-causal quantum computation have been considered in the literature, the approaches have so far only been focusing on the physicality of such processes, using matrices and other techniques from linear algebra. If these approaches are expressive, they however only provide a static and monolithic understanding of these processes. In this article, we propose a new formalism for non-causal, higher-order quantum processes. Based on a Curry-Howard interpetation, our proposal offers a computational interpretation that is both compositional and modular. In particular, we present Intuitionistic Unitary Linear Logic (IULL), a logic based on linear logic focusing on conservation of unitarity for higher order terms. We prove the coherence of IULLL, its completeness with regard to unitaries, and the admissibility of its cut rules. We finally discuss the validity of our approach by revisiting known non-causal quantum processes with IULL.

0.42

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.61
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

A quantum let within the lambda calculus

cs.LO quant-ph ·2026-08-29 ·Alejandro Díaz-Caro, Tomás Miguez
theory similarity 0.57
Abstract · 17 pages plus appendix with full proofs

Since the seminal work of Selinger and Valiron, the standard design for quantum lambda calculi has kept the quantum state outside the program: terms manipulate pointers to an external register. This is largely due to the difficulty of eliminating tensor products. For example, the calculus $λ_ρ^\circ$ embeds density matrices directly within terms, where terms carry the entire computation state, a feature particularly appealing for program verification. However, lacking a tensor elimination construct, it can neither access the individual qubits of a compound state nor discard them. Borgna showed that this inability to discard qubits makes the calculus strictly less expressive than the quantum lambda calculus of Selinger and Valiron. In this paper we show that tensor elimination is possible in this setting. The key observation is that the Pauli decomposition, combined with the spectral decomposition of the Pauli matrices, allows any $n$-qubit density matrix to be expressed as a real linear combination of tensor products of single-qubit density matrices. Exploiting this fact, we extend $λ_ρ^\circ$ with a construct $\mathrm{let}\ x^{\otimes n} = ρ \mathrm{in}\ t$, which binds each $x_i$ to a single-qubit density matrix arising from the decomposition of $ρ$. We equip the extended calculus with a rewrite system, a type system, and a denotational semantics, and prove Subject Reduction, Progress, Strong Normalisation, Soundness, and Adequacy. The new construct also recovers the missing ability to discard qubits, thereby restoring expressiveness. Moreover, we show that this is achieved in a physically principled way: a variable unused in $t$ is interpreted exactly as being partial-traced out, as dictated by the no-deleting theorem. We illustrate the resulting compositionality through quantum teleportation and the three-qubit bit-flip code.

0.35

Quantum computers will not be that different: A blueprint for quantum computer architecture at scale

cs.AR quant-phcs.NIeess.SY ·2026-09-17 ·Torsten Hoefler, Matthias Troyer
similarity 0.57
Abstract

Quantum computers are technologically novel and unusual, but at system scale they should be engineered using many of the same principles that govern classical heterogeneous accelerators. This paper argues that utility-scale quantum architecture is primarily a cost-performance problem across a coupled quantum-classical system, leading to a blueprint for scalable quantum processing unit (QPU) design. Our architecture blueprint is organized around clean logical abstractions, hiding details and complexity of physical qubit modalities below the instruction set architecture (ISA) boundary, and specializes recurring functions aggressively to minimize the cost for utility scale quantum computations. Its low-level implementation through specialized local hardware for control, readout, and quantum error correction (QEC) closely resembles the architecture of high-performance network stacks. One of our main insights is that the design principles and the resulting architecture closely follow established practice from classical computing and networking.

0.37

Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory

cs.AI quant-phcs.CC ·2026-08-11 ·Ming Yang
theory similarity 0.57
Abstract · Comments and suggestions are welcome on alphaXiv

We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication $B$, persistent instance-dependent memory $M$, and local work $D$; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity synopsis QA inherits the hidden-matching separation between $O(\log N)$ qubits and $Ω(\sqrt{N})$ classical boundary bits. Continual requirements auditing inherits a Max-$k$SAT streaming separation: a recurrent solver uses $O(\log^5 n\log(1/δ))$ qubits and polylogarithmic classical workspace to obtain a $0.7172$-approximation, whereas every classical one-pass finite-information solver attaining that ratio requires $Ω(\sqrt{n})$ coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses $n$ qubits, while every exact finite-state classical causal online realization satisfies $B+M \ge \frac{1}{2}n^2+(\frac{3}{2}-\log_2 3)n+O(1)$. The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

0.04

Rethinking Quantum Circuits

cs.IT quant-phcond-mat.mes-hallmath-ph+1 ·2026-08-19 ·Steven Rayan
similarity 0.57
Abstract · 75 pages, 26 figures (incl. cover figure), 10 tables; based on a four-lecture series delivered by the author during the Niels Bohr Quantum S…

These notes develop four interconnected ways of reading a quantum circuit. A circuit for us begins as an operational composition of gates; then, it becomes a diagram whose local equalities may be used as calculations; next, it becomes a protected process once errors, syndromes, and logical degrees of freedom are separated; and finally, it becomes geometric when its connectivity, topology, and boundary data are treated as physical design parameters. The development begins at the level of bits and qubits before appealing to Deutsch's and Grover's algorithms as basic examples of quantum circuits. With the basics in hand, we interpret quantum circuits diagramatically, leading us to compact closed string diagrams and the ZX-calculus. After that, we consider how to correct quantum circuits by introducing the Knill--Laflamme condition, homological surface codes, and related concepts with a view towards thinking of these as operations on diagrams. The lectures eventually arrive at the properties of hyperbolic quantum codes and the prospect of physical superconducting circuits emulating the negatively-curved lattices needed to support those codes. These mathematical ideas and physical experiments, taken together, represent one way to impart a geometric layer onto quantum circuits. By the very end, we bring the ideas nearly full circle by assessing the extent to which these device physics experiments operationalize the basic ZX diagrams encountered much earlier in the story. While the later material reports on original research, and while the discussion becomes increasingly mathematical as the sections progress, no prior knowledge of quantum information, quantum computing, or quantum error correction is actually assumed.

0.43

Quantum Advantage with Sign-Free Proofs: An Oracle Separation between $\mathsf{StoqMA}$ and $\mathsf{MA}$

cs.CC quant-phcs.DS ·2026-11-05 ·Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
theory similarity 0.57
Abstract · 21 pages, 3 figures

Several landmark oracle results (FOCS 2000, FOCS 2025, STOC 2026) establish strict separations along the chain $\mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}$, showing that quantum verification and quantum witnesses can each provide additional power over classical proof systems. These separations, however, use substantial coherent quantum computation, often through the quantum Fourier transform. We prove that a minimal quantum resource already suffices to outperform every classical verifier. Namely, we show the separation $$\mathsf{MA} \subsetneq \mathsf{StoqMA}$$ relative to a classical oracle. The class $\mathsf{StoqMA}$, introduced by Bravyi, Bessen, and Terhal (arXiv 2006), restricts the verifier to classical reversible computation, followed by a single Hadamard-basis measurement. Its power is closely tied to the complexity of stoquastic Hamiltonians, a sign-problem-free and seemingly more tractable class of quantum Hamiltonians. Our separating problem is to determine whether a sparse high-girth graph, given via an adjacency-list oracle, has a large or small Perron--Frobenius eigenvalue. This amounts to a ground-energy estimation task for a related stoquastic Hamiltonian. Our construction builds on a line of work on graph exploration problems with exponential quantum speedups, from welded trees (STOC 2003) to recent constructions (STOC 2021, arXiv 2026).

0.23

Unitary RQL Equals RQL

cs.CC quant-ph ·2026-10-05 ·Quinten Tupker
theory similarity 0.56
Abstract · 50 pages, 9 figures

Intermediate measurements let quantum computations discard information and reuse their workspace. Deferring all measurements can require storing their entire history, which need not preserve logarithmic space. Fefferman and Remscrim proved that measurements can nevertheless be eliminated with two-sided bounded error, and asked whether the same holds with one-sided error [FR21]. We prove RQLΓ = RQULΓ for the standard gate set Γ = {H, T, CNOT}, preserving polynomial time, logarithmic space, and exactly zero acceptance on no-instances. Our proof extends the density-matrix doubling method of Girish, Raz and Zhan [ GRZ21 ] to general channels, including resets and classical memory. We also prove measurement elimination for broader finite gate sets with exact inverses, including suitable gates with transcendental entries, and establish gate-set independence for a specified family of algebraic gate sets. A separate history-checking construction proves QMAL1,G = QUMAL1,G under explicit gate assumptions: measurements can also be eliminated from logarithmic-space quantum verification while preserving perfect completeness

0.32