Jacob Biamonte

What Minimal Structure Enables Quantum Computation?

Not all quantum systems support meaningful computation. The boundary between quantum physics and computation is structural: only specific patterns of interaction, representation, and control enable universal and trainable computation. My work makes this latent structure explicit for logical reasoning, programmability, and complexity analysis.

This occurs when three conditions jointly suffice:

• 1. A non-commutative interaction model enabling computational expressivity;
• 2. A compositional semantics linking physical dynamics to logical representation;
• 3. A controllable, hardware-compatible parameterization enabling algorithmic training.

Together, these criteria determine when physical models and architectures are universal, when compositional constructions are representable, and when variational regimes remain trainable. This research program develops along three corresponding axes: Model, Language, and Training.

Model: Universality in Physical Systems
This work established concrete criteria for computational universality in experimentally relevant ground-state models. In particular, the tunable transverse Ising interaction set {ZZ, Z, X} becomes universal when augmented with controllable XX couplings.

Within the Feynman–Kitaev Hamiltonian–circuit correspondence, this work proved QMA-completeness for sparse 2-local systems generated by the interaction sets {XX, ZZ, Z, X} and {ZX, XZ, Z, X}. Both families are accessible in superconducting qubit architectures. These results clarify structural limits of cost-Hamiltonian optimization and delineate when ground-state models support universal computation.

Language: Computation from Composition
This work derived an algebraic normal form unifying Penrose tensor networks, circuit models, and logic-to-Hamiltonian constructions within a single compositional framework. This provides:

• 1. A semantic bridge between physical Hamiltonians and logical computation
• 2. Graphical rewrite principles for physical consistency of processes, counting, and satisfiability
• 3. A formulation of tensor networks as a language of computation rather than merely a contraction scheme

This framework places quantum and classical tensor contraction within a shared compositional grammar.

Training: Variational Universality and Its Limits
This work proved that feed-forward variational quantum computation is universal, elevating it from a heuristic ansatz class to a formal model of computation. This work then identified principled, non-barren limits of trainability:

• 1. Reachability deficits: expressivity gaps that restrict accessible states and shape optimization landscapes
• 2. Saturation effects: structural plateaus that limit effective training

These results delineate regimes where variational circuits can and cannot train. In particular, reachability deficits explain why strong empirical performance often appears in statistically narrow, low-density regimes rather than generically across parameter space.

Selected external markers: Longuet-Higgins Paper Prize (2012); Editors’ Selection (Physical Review A, Letters Section, 2021; Communications Physics, 2019 Anniversary Collection); Plenary and named invited lectures (EPFL, 2022; Edward Shapiro Lecture Series, Pennsylvania State University, 2015); Associate Editor, ACM Transactions on Quantum Computing.