pith. sign in

arxiv: 2510.05557 · v2 · pith:VLKNUCSNnew · submitted 2025-10-07 · 🪐 quant-ph

Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources

Brent Harrison , Vishnu Iyer , Ojas Parekh , Kevin Thompson , Andrew Zhao This is my paper

Pith reviewed 2026-05-21 20:53 UTC · model grok-4.3

classification 🪐 quant-ph
keywords measurement-based quantum computationcircle graph statesfermionic Gaussian statesresource statesuniversalitystabilizer statesentanglement widthquantum computation complexity
0
0 comments X

The pith

Circle graph states are not efficiently universal for measurement-based quantum computation, assuming BQP is not equal to BPP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that circle graph states cannot serve as efficient universal resources for MBQC even though they are expressive. It establishes this by building a graph-theoretic correspondence to a subset of fermionic Gaussian states whose computational limitations are already known. A reader would care because universal resources are needed to turn MBQC into a practical quantum computing platform, and ruling out an entire family narrows the search. The result combines techniques for handling both stabilizer states and fermionic states in one framework.

Core claim

We articulate a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This correspondence transfers non-universality results from the fermionic domain, proving that circle graph states are not efficiently universal for MBQC assuming BQP ≠ BPP. The proof synthesizes methods that treat stabilizer states and fermionic Gaussian states together.

What carries the argument

The graph-theoretic correspondence that maps circle graph states onto a restricted class of fermionic Gaussian states and carries over their computational limitations.

If this is right

  • Any MBQC protocol that starts from circle graph states and applies only local Clifford operations, local Pauli measurements, and classical communication remains inside BPP.
  • Circle graph states cannot generate the full set of states needed for unbounded entanglement width under efficient local operations.
  • The non-universality result applies directly to any family of resource states that can produce circle graph states via the allowed operations.
  • Fermionic Gaussian state techniques become applicable to analyzing other graph-state families in MBQC.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same correspondence method could be tested on other named graph-state families to check their universality status.
  • Insights from this fermionic mapping might help classify which entanglement structures survive local Clifford reduction.
  • If the correspondence can be made tighter, it may yield new bounds on the classical simulability of specific MBQC circuits.

Load-bearing premise

A precise graph-theoretic correspondence exists between circle graph states and a certain subset of fermionic Gaussian states that transfers non-universality results from the fermionic domain.

What would settle it

An explicit efficient classical algorithm that uses local Clifford operations, local Pauli measurements, and classical communication on circle graph states to solve a BQP-complete problem would falsify the claim under the BQP ≠ BPP assumption.

read the original abstract

Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming $\mathsf{BQP} \neq \mathsf{BPP}$). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that circle graph states are not efficiently universal resources for measurement-based quantum computation (MBQC), assuming BQP ≠ BPP. This is established via a precise graph-theoretic correspondence between circle graph states and a subset of fermionic Gaussian states, which transfers non-universality results from the fermionic domain; the proof synthesizes techniques for simultaneously handling stabilizer states and fermionic Gaussian states.

Significance. If the correspondence is shown to preserve the operational structure of adaptive MBQC protocols, the result would clarify an open question on the universality of circle graphs as MBQC resources and provide bridging methods between stabilizer and Gaussian fermionic states with potential applications beyond MBQC.

major comments (2)
  1. [§4] §4 (graph-theoretic correspondence): the central transfer of non-universality requires that local Clifford operations, local Pauli measurements, and classical communication on the circle-graph side map to operations preserving both the Gaussian property and efficient classical simulability on the fermionic side; the manuscript must explicitly verify that the adaptive measurement protocol commutes with the bijection or embedding, as a static-state correspondence alone does not suffice.
  2. [§5] §5 (non-universality implication): the reduction to the assumption BQP ≠ BPP is load-bearing for the 'efficiently universal' claim, yet the manuscript provides no explicit error analysis or statement of the precise computational complexity class being ruled out once the fermionic simulability is transferred.
minor comments (2)
  1. [Abstract] The abstract states that techniques are synthesized to handle both stabilizer and Gaussian states simultaneously but does not identify the key technical innovation; a one-sentence clarification would improve readability.
  2. [§3] Notation for the fermionic Gaussian subset and the circle-graph embedding should be introduced with a small table or diagram to make the correspondence easier to follow.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and valuable comments on our manuscript. These points help us strengthen the presentation of the graph-theoretic correspondence and the complexity implications. We address each major comment below and will incorporate the suggested clarifications in the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (graph-theoretic correspondence): the central transfer of non-universality requires that local Clifford operations, local Pauli measurements, and classical communication on the circle-graph side map to operations preserving both the Gaussian property and efficient classical simulability on the fermionic side; the manuscript must explicitly verify that the adaptive measurement protocol commutes with the bijection or embedding, as a static-state correspondence alone does not suffice.

    Authors: We agree that an explicit verification of operational preservation is essential for the transfer of non-universality. The bijection in §4 is constructed via a graph-theoretic embedding that maps circle graphs to a restricted class of fermionic Gaussian states while preserving the stabilizer formalism and Gaussianity under local operations. Local Clifford gates and Pauli measurements on the graph-state side correspond to quadratic fermionic operations and parity measurements that remain within the simulable Gaussian class. To address the referee's concern directly, we will add a new subsection in §4 that explicitly demonstrates the commutation: we show that any adaptive MBQC protocol on circle graph states maps to an equivalent adaptive protocol on the fermionic side whose classical simulability is preserved at each step, including the classical communication of measurement outcomes. This will include a diagram and a short proof sketch confirming that the embedding commutes with the protocol. revision: yes

  2. Referee: [§5] §5 (non-universality implication): the reduction to the assumption BQP ≠ BPP is load-bearing for the 'efficiently universal' claim, yet the manuscript provides no explicit error analysis or statement of the precise computational complexity class being ruled out once the fermionic simulability is transferred.

    Authors: We acknowledge that the manuscript would benefit from a more precise statement of the complexity consequence. The argument proceeds by showing that efficient universality of circle graph states would allow efficient classical simulation of a class of fermionic Gaussian states that are known to be BPP-simulable, thereby placing BQP in BPP. In the revision we will expand §5 with an explicit statement that the result rules out efficient universality under the assumption BQP ≠ BPP, together with a brief error analysis: we bound the overhead of the simulation transfer (polynomial in the number of qubits and measurements) and confirm that any super-polynomial advantage in the MBQC protocol would yield a super-polynomial classical algorithm for the corresponding fermionic instance, contradicting the assumption. This addition will make the load-bearing reduction fully transparent. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses independent graph-theoretic correspondence synthesized from separate domains

full rationale

The paper's central step is the articulation of a precise graph-theoretic correspondence between circle graph states and a subset of fermionic Gaussian states, which is used to transfer non-universality results from the fermionic domain. This correspondence is constructed by synthesizing established techniques for stabilizer states and fermionic Gaussian states simultaneously, rather than by self-definition, parameter fitting to the target result, or load-bearing self-citation. The derivation does not reduce the claimed non-universality (under BQP ≠ BPP) to its own inputs by construction; the mapping is presented as an independent bridge between domains. The paper is self-contained against external benchmarks in graph theory and fermionic physics, with no steps that qualify as circular under the enumerated patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, invented entities, or ad-hoc axioms are described. The work rests on standard background results in quantum information and complexity theory.

axioms (2)
  • standard math Standard properties of stabilizer states, local Clifford operations, and local Pauli measurements in MBQC.
    Invoked to define the resource properties and operations allowed in the universality definition.
  • domain assumption Known computational limitations of certain fermionic Gaussian states.
    Transferred via the new correspondence to reach the non-universality conclusion.

pith-pipeline@v0.9.0 · 5721 in / 1384 out tokens · 65241 ms · 2026-05-21T20:53:55.659523+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Structure of Circle Graph States

    quant-ph 2026-03 unverdicted novelty 7.0

    Circle graphs are closed under r-local complementation and bipartite circle graph states correspond one-to-one with planar code states whose MBQC is classically simulable.