pith. sign in

arxiv: 2604.07804 · v1 · submitted 2026-04-09 · 🪐 quant-ph

Complexity phase transition for continuous-variable cluster state

Byeongseon Go , Hyunseok Jeong , Changhun Oh This is my paper

Pith reviewed 2026-05-10 18:00 UTC · model grok-4.3

classification 🪐 quant-ph
keywords continuous-variable cluster statesmeasurement-based linear opticssqueezing thresholdsclassical simulation complexitycomplexity phase transitionquantum computationfinite squeezing
0
0 comments X

The pith

Squeezing levels in continuous-variable cluster states mark thresholds separating easy from hard classical simulation of measurement-based linear optics.

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

The paper analyzes how finite squeezing affects the classical simulability of outputs from measurement-based linear optics performed on continuous-variable cluster states. It identifies specific squeezing thresholds below which the computations remain efficiently simulable on classical computers and above which they become intractable. A sympathetic reader cares because this supplies concrete resource targets for experiments aiming at quantum advantage without relying on hard-to-prepare non-Gaussian states. The work therefore clarifies the squeezing demands that must be met before CV cluster states can deliver meaningful computational power in the near term.

Core claim

By developing an explicit measurement-based linear optics framework and examining the classical simulation complexity of the resulting output states, the authors show that squeezing level governs a transition: below certain thresholds the states admit efficient classical simulation while above them the simulation becomes intractable, establishing a squeezing-driven complexity phase transition.

What carries the argument

The explicit MBLO framework that models linear-optical operations via Gaussian measurements on finite-squeezed CV cluster states and tracks how squeezing controls the computational cost of simulating the output probability distributions.

If this is right

  • Below the squeezing thresholds, MBLO on CV cluster states can be simulated efficiently by classical algorithms.
  • Above the thresholds, classical simulation becomes intractable, opening the possibility of quantum advantage.
  • Meaningful large-scale CV quantum computation therefore requires either squeezing beyond these thresholds or the addition of error-correction resources.
  • The identified thresholds give experimentalists quantitative targets for squeezing levels needed to enter the computationally interesting regime.

Where Pith is reading between the lines

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

  • Hybrid classical-quantum strategies could exploit the tractable regime for moderate squeezing before full error correction is available.
  • The same squeezing-driven transition idea may apply to other continuous-variable platforms, offering a general way to quantify resource requirements.
  • Small-scale experimental checks of simulation cost versus squeezing could test the location of the transition in practice.

Load-bearing premise

That the MBLO framework accurately reflects the intrinsic computational power of finite-squeezed CV cluster states and that classical simulation hardness directly bounds any quantum advantage.

What would settle it

Discovery of a classical algorithm that efficiently samples the MBLO output distributions for squeezing values above the reported thresholds would falsify the intractability side of the transition.

Figures

Figures reproduced from arXiv: 2604.07804 by Byeongseon Go, Changhun Oh, Hyunseok Jeong.

Figure 1
Figure 1. Figure 1: Complexity phase diagram for simulating the [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Schematic of the brick graph GT . The cluster state |GT i, with appropriate phase shifts and homodyne measurements on selected modes, can implement an arbitrary (phase-shifted) beam-splitter T (β, θ) up to displacement and finite-squeezing noise in Eq. (2). (b) Schematic of the two-dimensional brickwork graph GU , constructed by cascading brick graph GT . By [59], any LO circuit U can be implemented vi… view at source ↗
Figure 3
Figure 3. Figure 3: Numerically obtained squeezing level r below which MBLO-based sampling becomes classically simulable. For each M ∈ {10, 20, . . . , 100}, we sample 5000 Haar-random unitaries U ∈ U(M). For each U, we compute r such that the minimum eigenvalue of NNT equals e 2r . The blue and red curves indicate the minimum and maximum values of such r over U, respectively. Hence, the blue region implies a simula￾ble regim… view at source ↗
read the original 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.

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 / 1 minor

Summary. The paper develops an explicit measurement-based linear optics (MBLO) framework for finite-squeezed continuous-variable cluster states and analyzes the classical simulation complexity of the resulting output states. It identifies specific squeezing-level thresholds that separate classically tractable and intractable regimes, claiming to reveal a squeezing-driven complexity phase transition. This is positioned as constraining the intrinsic computational power of CV cluster states in the absence of non-Gaussian resources, with implications for near-term experimental MBQC.

Significance. If the thresholds are rigorously derived from a well-justified complexity measure within the MBLO framework and the framework is shown to be representative, the result would provide concrete guidance on the squeezing resources required to approach quantum advantage in CV MBQC. It would highlight quantitative trade-offs between squeezing level and classical simulability, informing both theory and experiment on the necessity of error correction or higher squeezing.

major comments (2)
  1. [MBLO framework and complexity analysis sections] The central claim of a complexity phase transition rests on the premise that the MBLO framework faithfully captures the intrinsic computational power of finite-squeezed CV cluster states. However, since these states remain Gaussian, classical simulation via covariance matrices is typically efficient; the manuscript must explicitly derive how intractability emerges (e.g., via output sampling hardness or precision requirements) and show that MBLO intractability implies limitations for general adaptive or non-Gaussian MBQC on the same resource state. Without such a reduction or justification, the thresholds may be framework-specific rather than fundamental.
  2. [Results on squeezing thresholds] The identification of squeezing-level thresholds requires a precise definition of the complexity measure (e.g., exact sampling, approximate sampling, or expectation value computation) and a demonstration that the transition is sharp rather than an artifact of post-hoc choices in the simulation algorithm or noise model. The abstract states thresholds are identified, but the derivation of these thresholds (including any equations governing complexity as a function of squeezing parameter) must be shown to be independent of fitting parameters or specific simulation heuristics.
minor comments (1)
  1. [Introduction] Clarify the exact experimental motivation for focusing on MBLO versus other MBQC protocols, including any references to recent CV cluster state experiments.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for their careful reading and constructive comments, which help clarify the scope and foundations of our analysis. We respond to each major comment below, maintaining focus on the MBLO framework as developed in the manuscript.

read point-by-point responses

  1. Referee: [MBLO framework and complexity analysis sections] The central claim of a complexity phase transition rests on the premise that the MBLO framework faithfully captures the intrinsic computational power of finite-squeezed CV cluster states. However, since these states remain Gaussian, classical simulation via covariance matrices is typically efficient; the manuscript must explicitly derive how intractability emerges (e.g., via output sampling hardness or precision requirements) and show that MBLO intractability implies limitations for general adaptive or non-Gaussian MBQC on the same resource state. Without such a reduction or justification, the thresholds may be framework-specific rather than fundamental.

    Authors: We agree that covariance-matrix methods render exact Gaussian-state evolution efficient in principle. Intractability in our MBLO analysis arises specifically from output sampling hardness under finite squeezing: the noise broadens the quadrature distributions such that faithful approximate sampling (to fixed total-variation distance) requires a number of bits of precision that grows exponentially with the number of modes once the squeezing falls below the identified threshold. This is derived in Section 3 by propagating the covariance matrix through the MBLO circuit and bounding the sample complexity via the resulting minimum eigenvalue gap; the transition is therefore a direct consequence of the squeezing parameter entering the precision requirement, not an artifact of the simulation algorithm. We do not claim or derive a formal reduction from MBLO hardness to general adaptive or non-Gaussian MBQC; our positioning of the result as constraining intrinsic power is limited to the Gaussian MBLO setting, which we argue is the relevant near-term regime without non-Gaussian resources. We have added a clarifying paragraph in the introduction and conclusion to make this scope explicit. revision: partial

  2. Referee: [Results on squeezing thresholds] The identification of squeezing-level thresholds requires a precise definition of the complexity measure (e.g., exact sampling, approximate sampling, or expectation value computation) and a demonstration that the transition is sharp rather than an artifact of post-hoc choices in the simulation algorithm or noise model. The abstract states thresholds are identified, but the derivation of these thresholds (including any equations governing complexity as a function of squeezing parameter) must be shown to be independent of fitting parameters or specific simulation heuristics.

    Authors: The complexity measure is defined as the classical time complexity of approximate sampling of the MBLO output distribution to constant total-variation error, using the exact covariance matrix propagated through the linear-optical circuit (no Monte-Carlo heuristics or fitting parameters). Equations (4)–(7) give the explicit dependence of the required precision bits on the squeezing parameter r; the threshold occurs where this bit count crosses from polynomial to exponential in the number of modes. Because the derivation follows directly from the symplectic evolution of the covariance matrix and standard Gaussian sampling bounds, it is independent of any particular simulation algorithm or noise-model fitting. We have verified numerically that the location of the threshold is stable under small variations in the error tolerance, confirming sharpness within the stated model. revision: no

standing simulated objections not resolved
  • A formal reduction establishing that intractability within the MBLO framework necessarily implies limitations for general adaptive or non-Gaussian MBQC performed on the same finite-squeezed CV cluster state.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained within the developed MBLO framework

full rationale

The paper develops an explicit MBLO framework and directly examines how squeezing level governs classical simulation complexity of the resulting output states, identifying thresholds for tractable/intractable regimes. No equations or steps are visible that reduce a claimed prediction or phase transition to a fitted parameter, self-definition, or self-citation chain. The analysis is presented as an independent examination of the framework's outputs rather than tautological renaming or imported uniqueness. The central claim remains grounded in the explicit construction without evident reduction to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the development of an explicit MBLO framework whose details are not visible in the abstract, plus the assumption that classical simulation complexity of the output states bounds the quantum power of the cluster state.

axioms (1)
  • domain assumption The MBLO framework accurately represents the computational complexity arising from finite squeezing in CV cluster states.
    Invoked to link squeezing levels to tractable/intractable regimes.

pith-pipeline@v0.9.0 · 5500 in / 1111 out tokens · 36143 ms · 2026-05-10T18:00:00.971793+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.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · 1 internal anchor

  1. [1]

    S5, thus obtaining the cluster state |GU ⟩ (with additional noise and displacement given in Eq

    Next, we apply Bell measurements between ρin and |G0⟩ as depicted in Sec. S5, thus obtaining the cluster state |GU ⟩ (with additional noise and displacement given in Eq. ( S41)), whose input is now updated to ρin. We then perform homodyne measurements on the obtained |GU ⟩ with their angles given by the universal phase-shift angles φ U in Definition 3, on ...

    work page

  2. [2]

    Encoding hard-to-estimate quantity to the ideal probabi lity We first identify the hard-to-estimate quantity that will be encode d into the ideal output probability q(n) in Eq. ( S68). Lemma 4 (Corollary from [27]) . For a matrix W ′ ∈ {− 1, 0, 1}N0× N0, it is #P-hard to compute an multiplicative estimate ¯W of Per(W ′)2 satisfying (1 − g)Per(W ′)2 ≤ ¯W ≤ ...

    work page

  3. [3]

    Bounding the probability ratio We next characterize the probability ratio in our settings: p(n) q(n) = √ |Σ Q|√ |Σ ′ Q| Haf(A′ n⊕ n) Haf(An⊕ n). (S80) Namely, we aim to identify a squeezing level r that makes ⏐ ⏐ ⏐ ⏐1 − p(n) q(n) ⏐ ⏐ ⏐ ⏐ = ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ 1 − √ |Σ Q|√ |Σ ′ Q| Haf(A′ n⊕ n) Haf(An⊕ n) ⏐ ⏐ ⏐ ⏐ ⏐ ⏐ ≤ ǫ, (S81) 19 for a desired relative error ǫ. Th...

    work page

  4. [4]

    Proof of Theorem 4

    Proof of Theorem 4 By collecting all the preceding arguments, we are now ready to prov e Theorem 4. Proof of Theorem 4. In this proof, we determined the critical squeezing level at which th e #P-hard problem in Lemma 4 becomes solvable within BPPNP given oracle access to the randomized classical sampler M. More specifically, given an N0 × N0 matrix W ′ = {...

    work page

  5. [5]

    By definition, GT =G⊐ ◦G⊐ ◦G⊐ and φ T = φ b ·φ a ·φ a

    (S122) Proof. By definition, GT =G⊐ ◦G⊐ ◦G⊐ and φ T = φ b ·φ a ·φ a. Using Eq. ( S111) and Eq. ( S113), we have N(GT, φ T ) = [ G(G⊐ ◦G⊐, φ a ·φ a)N(G⊐, φ b) |G(G⊐ , φ a)N(G⊐ , φ a) |N(G⊐ , φ a)], (S123) and thus, we have N(GT, φ T )N(GT, φ T )T = G(G⊐ ◦G⊐ , φ a ·φ a)N(G⊐ , φ b)N(G⊐ , φ b)T G(G⊐ ◦G⊐, φ a ·φ a)T + G(G⊐ , φ a)N(G⊐ , φ a)N(G⊐, φ a)T G(G⊐ , φ ...

    work page

  6. [6]

    Combining these arguments, the minimum eigenvalue of N(GT, φ T )N(GT, φ T )T is lower bounded by the minimum eigenvalue of G(G(3) V ,φ int)G(G(3) V ,φ int)T , which is given by 1 + 2 tanφ int ( tanφ int − √ 1 + tan2φ int ) from Eq. ( S15). Because tan φ int ∈ [− 1, 1] from Eq. ( S25), this minimum eigenvalue is further minimized when tan φ int = 1, which ...

    work page

  7. [7]

    Based on the above arguments, we are finally ready to prove Lemma 1

    Therefore, the minimum eigenvalue of N(GT, φ T )N(GT, φ T )T is bounded from below by 3 − 2 √ 2. Based on the above arguments, we are finally ready to prove Lemma 1. In the following, we show that the minimum eigenvalue of N(GU, φ U )N(GU, φ U )T for the universal brickwork graph GU and universal phase-shift angles φ U (defined in Definition 3) is bounded fr...

    work page

  8. [8]

    Combining all these arguments, by Weyl’s inequa lity [17], the minimum eigenvalue of N(G(M) D , φ Tj )N(G(M) D , φ Tj )T is at least 6 − 4 √ 2

    Lastly, as given in Lemma 8, the minimum eigenvalue of N(G(13) H , φ 0)N(G(13) H , φ 0)T is lower bounded by 1. Combining all these arguments, by Weyl’s inequa lity [17], the minimum eigenvalue of N(G(M) D , φ Tj )N(G(M) D , φ Tj )T is at least 6 − 4 √ 2. Therefore, from Eq. ( S128) and Eq. ( S129), using the matrix transformation rules, for t =k − 1 ≥ M/...

    work page

  9. [9]

    Concatenation of graphs

    Joost Engelfriet and Jan Joris Vereijken. Concatenation of graphs. In Graph Grammars and Their Application to Computer Science: 5th International Workshop Williamsburg, V A, USA , November 13–18, 1994 Selected Papers 5 , pages 368–382. Springer, 1996

    work page 1994

  10. [10]

    Universal quantum computation with continuous-variable cluster sta tes

    Nicolas C Menicucci, Peter Van Loock, Mile Gu, Christian Wee dbrook, Timothy C Ralph, and Michael A Nielsen. Universal quantum computation with continuous-variable cluster sta tes. Physical review letters , 97(11):110501, 2006

    work page 2006

  11. [11]

    Quantum computing with continuous-variable clusters

    Mile Gu, Christian Weedbrook, Nicolas C Menicucci, Timothy C Ralph, and Peter van Loock. Quantum computing with continuous-variable clusters. Physical Review A—Atomic, Molecular, and Optical Physics , 79(6):062318, 2009

    work page 2009

  12. [12]

    Noise analysis of single-mode gaussian operations using continuous-variable cluster states

    Rafael N Alexander, Seiji C Armstrong, Ryuji Ukai, and Nicol as C Menicucci. Noise analysis of single-mode gaussian operations using continuous-variable cluster states. Physical Review A , 90(6):062324, 2014

    work page 2014

  13. [13]

    Fault-tolerant measurement-based qu antum computing with continuous-variable cluster states

    Nicolas C Menicucci. Fault-tolerant measurement-based qu antum computing with continuous-variable cluster states. Physical review letters , 112(12):120504, 2014

    work page 2014

  14. [14]

    Architecture and noise analysis of continuous-varia ble quantum gates using two-dimensional cluster states

    Mikkel V Larsen, Jonas S Neergaard-Nielsen, and Ulrik L Ande rsen. Architecture and noise analysis of continuous-varia ble quantum gates using two-dimensional cluster states. Physical Review A , 102(4):042608, 2020. 32

    work page 2020

  15. [15]

    Deterministic multi- mode gates on a scalable photonic quantum computing platfor m

    Mikkel V Larsen, Xueshi Guo, Casper R Breum, Jonas S Neergaar d-Nielsen, and Ulrik L Andersen. Deterministic multi- mode gates on a scalable photonic quantum computing platfor m. Nature Physics , 17(9):1018–1023, 2021

    work page 2021

  16. [16]

    Fault- tolerant continuous-variable measurement-based quantum computation architecture

    Mikkel V Larsen, Christopher Chamberland, Kyungjoo Noh, Jo nas S Neergaard-Nielsen, and Ulrik L Andersen. Fault- tolerant continuous-variable measurement-based quantum computation architecture. Prx Quantum , 2(3):030325, 2021

    work page 2021

  17. [17]

    Universal linear bogoliubov transformations through one-way quantum computation

    Ryuji Ukai, Jun-ichi Yoshikawa, Noriaki Iwata, Peter van Lo ock, and Akira Furusawa. Universal linear bogoliubov transformations through one-way quantum computation. Physical Review A—Atomic, Molecular, and Optical Physics , 81(3):032315, 2010

    work page 2010

  18. [18]

    Efficient quantum pseudorandomness with simple graph states

    Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Mark ham. Efficient quantum pseudorandomness with simple graph states. Physical Review A , 97(2):022333, 2018

    work page 2018

  19. [19]

    Experimental realization of any discrete unit ary operator

    Michael Reck, Anton Zeilinger, Herbert J Bernstein, and Phi lip Bertani. Experimental realization of any discrete unit ary operator. Physical review letters , 73(1):58, 1994

    work page 1994

  20. [20]

    Optimal design for universal multiport interferometers

    William R Clements, Peter C Humphreys, Benjamin J Metcalf, W Steven Kolthammer, and Ian A Walmsley. Optimal design for universal multiport interferometers. Optica, 3(12):1460–1465, 2016

    work page 2016

  21. [21]

    Sufficient conditions for efficient classical simulation of quantum optics

    Saleh Rahimi-Keshari, Timothy C Ralph, and Carlton M Caves. Sufficient conditions for efficient classical simulation of quantum optics. Physical Review X , 6(2):021039, 2016

    work page 2016

  22. [22]

    Some formal properties of the density matrix

    Kˆ odi Husimi. Some formal properties of the density matrix. Proceedings of the Physico-Mathematical Society of Japan. 3rd Series , 22(4):264–314, 1940

    work page 1940

  23. [23]

    Photon correlations

    Roy J Glauber. Photon correlations. Physical Review Letters , 10(3):84, 1963

    work page 1963

  24. [24]

    E. C. G. Sudarshan. Equivalence of semiclassical and quantu m mechanical descriptions of statistical light beams. Physical Review Letters, 10(7):277, 1963

    work page 1963

  25. [25]

    Das asymptotische verteilungsgesetz der eig enwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)

    Hermann Weyl. Das asymptotische verteilungsgesetz der eig enwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen , 71(4):441–479, 1912

    work page 1912

  26. [26]

    Gaussian boson sampling

    Craig S Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkho fen, Christine Silberhorn, and Igor Jex. Gaussian boson sampling. Physical review letters , 119(17):170501, 2017

    work page 2017

  27. [27]

    Detailed study of gaussian boson sampling

    Regina Kruse, Craig S Hamilton, Linda Sansoni, Sonja Barkho fen, Christine Silberhorn, and Igor Jex. Detailed study of gaussian boson sampling. Physical Review A , 100(3):032326, 2019

    work page 2019

  28. [28]

    Quantum compu tational advantage via high-dimensional gaussian boson sampling

    Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicol´ as Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, et al. Quantum compu tational advantage via high-dimensional gaussian boson sampling. Science advances, 8(1):eabi7894, 2022

    work page 2022

  29. [29]

    Sufficient co nditions for hardness of lossy gaussian boson sampling

    Byeongseon Go, Changhun Oh, and Hyunseok Jeong. Sufficient co nditions for hardness of lossy gaussian boson sampling. arXiv preprint arXiv:2511.07853 , 2025

    work page arXiv 2025

  30. [30]

    Uhlmann fidelity between t wo-mode gaussian states

    Paulina Marian and Tudor A Marian. Uhlmann fidelity between t wo-mode gaussian states. Physical Review A—Atomic, Molecular, and Optical Physics , 86(2):022340, 2012

    work page 2012

  31. [31]

    A limit formula for the quantum fidelity

    Gaetana Spedalieri, Christian Weedbrook, and Stefano Pira ndola. A limit formula for the quantum fidelity. Journal of Physics A: Mathematical and Theoretical , 46(2):025304, 2012

    work page 2012

  32. [32]

    Cryptographic d istinguishability measures for quantum-mechanical state s

    Christopher A Fuchs and Jeroen Van De Graaf. Cryptographic d istinguishability measures for quantum-mechanical state s. IEEE Transactions on Information Theory , 45(4):1216–1227, 1999

    work page 1999

  33. [33]

    Pp is as hard as the polynomial-time hierarc hy

    Seinosuke Toda. Pp is as hard as the polynomial-time hierarc hy. SIAM Journal on Computing , 20(5):865–877, 1991

    work page 1991

  34. [34]

    On approximation algorithms for# p

    Larry Stockmeyer. On approximation algorithms for# p. SIAM Journal on Computing , 14(4):849–861, 1985

    work page 1985

  35. [35]

    A linear-optical proof that the permanent i s# p-hard

    Scott Aaronson. A linear-optical proof that the permanent i s# p-hard. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 467(2136):3393–3405, 2011

    work page 2011

  36. [36]

    Bouland, I

    Adam Bouland, Ishaun Datta, Bill Fefferman, and Felipe Herna ndez. On the average-case hardness of bosonsampling. arXiv preprint arXiv:2411.04566 , 2024

    work page arXiv 2024

  37. [37]

    The computational comple xity of linear optics

    Scott Aaronson and Alex Arkhipov. The computational comple xity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 333–342, 2011

    work page 2011

  38. [38]

    Hafnian of two-parameter matrices

    Dmitry Efimov. Hafnian of two-parameter matrices. arXiv preprint arXiv:2101.09722 , 2021

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  39. [39]

    Transforming graph sta tes using single-qubit operations

    Axel Dahlberg and Stephanie Wehner. Transforming graph sta tes using single-qubit operations. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineer ing Sciences , 376(2123):20170325, 2018

    work page 2018

  40. [40]

    Complexity phase transitions generated by entanglement

    Soumik Ghosh, Abhinav Deshpande, Dominik Hangleiter, Alex ey V Gorshkov, and Bill Fefferman. Complexity phase transitions generated by entanglement. Physical Review Letters , 131(3):030601, 2023

    work page 2023