Complexity phase transition for continuous-variable cluster state
Byeongseon Go, Hyunseok Jeong, Changhun Oh
Abstract
Continuous-variable (CV) cluster states offer a promising platform for large-scale measurement-based quantum computations (MBQC). However, finite squeezing inevitably introduces Gaussian noise during MBQC. While fault-tolerant MBQC schemes exist in principle, they require the scalable incorporation of non-Gaussian resources, such as GKP states, which remain experimentally challenging. Consequently, a central question at this stage is how finite squeezing fundamentally constrains the intrinsic computational power of CV cluster states themselves. In this work, we address this question by analyzing the classical complexity of measurement-based linear optics (MBLO) implemented with such states, motivated by its near-term feasibility and recent experimental progress. We develop an explicit MBLO framework and examine how the squeezing level governs the complexity of the classical simulation of the resulting output states. Specifically, we identify squeezing-level thresholds that delineate classically tractable and intractable regimes, thereby revealing a squeezing-driven complexity phase transition. These findings advance our understanding of the squeezing resources necessary for meaningful quantum computation in current experimental regimes. Furthermore, they underscore the critical need to either scale the squeezing level or integrate error-correction schemes to achieve reliable, large-scale quantum computation with CV cluster states.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper identifies a squeezing-driven complexity phase transition for measurement-based linear optics (MBLO) on continuous-variable (CV) cluster states. The central result is a complexity phase diagram showing three distinct regimes as a function of the squeezing level *r*:
1. Easiness regime (Theorem 1): For *r* ≤ O(log M), MBLO output distributions can be efficiently classically simulated using the Rahimi-Keshari et al. P-function criterion.
2. Hardness regime I (Theorem 2): For *r* ≥ Ω(log M), classical simulation within inverse-polynomial total variation distance is hard, assuming hardness of approximate Gaussian boson sampling (GBS).
3. Hardness regime II (Theorem 3): For *r* ≥ Ω(M^Λ) for any constant Λ > 0, classical simulation implies collapse of the polynomial hierarchy (PH), a stronger/unconditional-style hardness result.
The paper develops an explicit MBLO framework using a brickwork graph architecture, provides systematic graph-based noise analysis, and derives the noise accumulation properties that underlie both results.
Methodological Rigor
The theoretical framework is carefully constructed. The authors build from elementary teleportation schemes on CV cluster states to a full universal brickwork decomposition for linear optical circuits, following the Clements et al. decomposition. The input-output relation (Eq. 2) cleanly separates the ideal transformation, finite-squeezing noise, and displacement terms.
Easiness proof: The key technical ingredient (Lemma 1) shows that the minimum eigenvalue of NN^T grows as Ω(M), arising from the Ω(M) circuit depth required for universality. This is combined with the P-function positivity criterion of Rahimi-Keshari et al. to establish classical simulability. The proof is rigorous and the graph-based decomposition of the noise matrix (Eq. 9) is elegant.
Hardness proof I: The approach bounds the total variation distance between the noisy MBLO output and the ideal GBS output using quantum fidelity (Fuchs-van de Graaf inequality), then leverages the conjectured hardness of approximate GBS. The bound (Eq. 10) cleanly shows exponential decay of the TVD error with squeezing level.
Hardness proof II: Uses Stockmeyer's reduction to show that oracle access to an MBLO sampler would enable multiplicative estimation of permanents of {-1,0,1} matrices (a #P-hard problem). The embedding strategy from Bouland et al. (2024) of a small hard matrix into a larger unitary is employed, reducing the required squeezing from exponential to sub-exponential (Ω(M^Λ)).
The supplemental material (32 pages) provides complete proofs with all technical lemmas, enhancing reproducibility and verifiability.
Potential Impact
Near-term experimental guidance: The paper provides concrete squeezing thresholds that experimentalists can target. The numerical analysis in Figure 3 shows that for M = 100 modes, squeezing levels of ~5-7 dB suffice for classical simulability, which is within current experimental reach (~10-15 dB). This directly informs the experimental community about what constitutes a meaningful demonstration.
Theoretical significance: The identification of matching O(log M) thresholds for both easiness and hardness (Theorems 1 and 2) is a particularly clean result. While the thresholds don't exactly match (the easiness threshold is a concrete O(log M) and the hardness threshold is also Ω(log M) but under a conjecture), the gap appears narrow, suggesting the phase transition is relatively sharp.
Broader implications: The work underscores that finite-squeezing noise fundamentally constrains CV cluster states and that the required squeezing scales logarithmically with system size for universal MBLO—a sobering result suggesting that maintaining quantum advantage requires either scaling squeezing or incorporating error correction (e.g., GKP states).
Timeliness & Relevance
This work is highly timely given:
The paper fills an important niche: between the idealized theory of CV MBQC and the noisy reality of current experiments, specifically for the experimentally accessible regime of Gaussian operations.
Strengths
1. Clean phase diagram: The matching Θ(log M) scaling for easiness and hardness thresholds provides a sharp characterization.
2. Explicit constructive framework: The brickwork graph construction with explicit phase-shift angles is immediately usable.
3. Multiple hardness levels: Two tiers of hardness under different assumptions (conjectured GBS hardness vs. PH non-collapse) provide a nuanced picture.
4. Practical numerical analysis: Figure 3 bridges theory and experiment.
5. Comprehensive supplemental material: Full proofs for all results.
Limitations
1. Framework specificity: The easiness result (Theorem 1) applies only to the specific brickwork MBLO architecture. The authors acknowledge this and argue analogous behavior should hold generally, but this remains unproven.
2. Gap between Theorems 2 and 3: The hardness regimes rely on different assumptions with different squeezing thresholds (Ω(log M) vs. Ω(M^Λ)), leaving a large intermediate regime where the complexity status depends on which conjectures one accepts.
3. No photon loss analysis: The framework addresses finite-squeezing noise but does not incorporate photon loss, which is important in practice.
4. Asymptotic nature: The O(log M) threshold scaling means current experiments (with fixed squeezing ~5-15 dB) will eventually fall in the easy regime as M grows, which is somewhat pessimistic for the field.
5. Comparison with Ref. [41]: The relationship to the prior MBLO hardness result of Alexander et al. could be more precisely delineated.
Overall Assessment
This is a technically solid paper that provides an important theoretical characterization of the computational power of CV cluster states as a function of squeezing. The results are well-motivated by experimental progress and provide actionable guidance. The complexity phase transition picture is compelling, though the gap between different hardness regimes and the restriction to a specific MBLO architecture limit the completeness of the characterization.
Generated Apr 10, 2026
Comparison History (48)
Paper 1 makes broader and more concrete contributions: it identifies a new classically tractable regime for fermionic systems with magic inputs, provides practical benchmarks matching quantum hardware statistical limits, applies results to real trapped-ion experiments and quantum chemistry (geminal wavefunctions), and directly sharpens the quantum advantage boundary. Its results span quantum simulation, complexity theory, and quantum chemistry. Paper 2 addresses an important but narrower question about squeezing thresholds in CV cluster states, providing theoretical phase transitions but with less immediate practical impact and a more specialized scope.
Paper 1 offers a sharper, more technically constructive advance: it identifies a nontrivial intermediate regime where “magic” fermionic inputs remain classically simulable, with rigorous bounds, explicit Pfaffian reductions, and concrete estimators matching quantum shot noise. It also ties directly to near-term benchmarking (trapped-ion quenches) and to quantum chemistry subroutines (APSG overlaps), broadening applicability across quantum simulation and chemistry. Paper 2 is timely and relevant, but its contribution is more diagnostic/threshold-setting for CV MBQC and likely depends on modeling assumptions; it is less methodologically distinctive and less immediately enabling than Paper 1’s explicit dequantization tools.
Paper 2 likely has higher impact: it links an experimentally central resource (finite squeezing in CV cluster states) to a concrete complexity phase transition, directly informing near-term continuous-variable MBQC/photonic experiments and guiding resource targets and error-correction needs. Its implications span quantum optics, complexity theory, and near-term quantum advantage. Paper 1 is methodologically strong and settles optimal query complexities across access models, but is more specialized (property testing/quantum algorithms) with less immediate experimental applicability and narrower cross-field reach.
Paper 2 addresses a fundamental question about the computational power of continuous-variable quantum systems, identifying squeezing-driven complexity phase transitions that directly inform experimental requirements for quantum advantage. This connects quantum complexity theory with practical CV quantum computing platforms that have seen significant experimental progress. While Paper 1 provides a useful noise characterization method, Paper 2's results have broader theoretical implications across quantum computing, complexity theory, and experimental quantum optics, and are more timely given the rapid development of CV quantum computing platforms.
Paper 2 likely has higher impact: it targets an urgent, experimentally relevant bottleneck in continuous-variable quantum computing—finite squeezing—and provides a clear, testable “phase transition” threshold separating classically simulable vs potentially quantum-advantage regimes. This directly informs near-term experiments and resource requirements, with broad implications across MBQC, photonics, complexity theory, and fault tolerance. Paper 1 is mathematically substantive for 2-RDM theory beyond particle-number conservation, but its applications are narrower and adoption may be limited to specialized quantum chemistry/many-body communities.
Paper 2 addresses a fundamental, long-standing theoretical issue (the representability problem) and extends its solution to non-particle-number-conserving systems. This provides a unified framework with broad, direct applications across quantum chemistry, condensed matter physics, and molecular physics. Paper 1, while important for continuous-variable quantum computing, focuses on a specific architecture and noise thresholds, giving it a narrower scope of impact compared to the foundational theoretical advance in many-body physics presented in Paper 2.
Paper 2 addresses a more practically relevant and timely question about continuous-variable quantum computing, identifying squeezing-driven complexity phase transitions that directly inform experimental efforts in near-term quantum computation. It bridges theory and experiment by providing actionable thresholds for a leading platform (CV cluster states), has broader impact across quantum computing, quantum optics, and complexity theory communities, and addresses the pressing question of when quantum advantage is achievable. Paper 1, while mathematically rigorous and resolving an open question about replica thresholds, addresses a more niche information-theoretic question with less immediate experimental or practical relevance.
Paper 1 offers an empirical, experimentally validated solution to a critical bottleneck in quantum computing: measurement-induced errors in dynamic circuits. Its demonstration on up to 20 qubits and immediate applicability to near-term quantum algorithms and foundational fault-tolerance gives it a broader and more immediate real-world impact. While Paper 2 provides valuable theoretical bounds for a specific platform (continuous-variable cluster states), Paper 1's methodology directly advances the practical realization of quantum error correction across multiple hardware architectures.
Paper 2 is likely higher impact: it links an experimentally central limitation (finite squeezing in CV cluster states) to a sharp computational-complexity phase transition with explicit thresholds, directly informing near-term experimental roadmaps and claims of quantum advantage in MBQC/linear optics. The result is broadly relevant across quantum optics, complexity theory, and near-term quantum computing, and is timely given active CV photonics progress. Paper 1 offers a valuable structural clarification for barren-plateau analyses and objective design, but its immediate real-world leverage and cross-field breadth are narrower and its evidence appears more limited to theory plus a specific numerical case study.
Paper 2 likely has higher impact: it tackles a timely, experimentally central limitation of CV cluster-state MBQC (finite squeezing) and provides concrete complexity thresholds separating classically simulable vs hard regimes, directly informing near-term experiments and resource targets. The “complexity phase transition” framing is broadly relevant across quantum optics, MBQC, and computational complexity, with clear real-world implications for when CV platforms can demonstrate advantage. Paper 1 offers elegant theory for Mpemba effects in QITE and useful criteria for faster state prep, but its impact is narrower and more dependent on QITE adoption and practical algorithms.