Quantum complexity resource in Gaussian boson sampling: Core structure of the semidefinite program

• URL: http://arxiv.org/abs/2606.29739v1
• Date: Mon, 29 Jun 2026 03:25:20 GMT
• Title: Quantum complexity resource in Gaussian boson sampling: Core structure of the semidefinite program
• Abstract summary: We present a rigorous analysis of the structure of the quantum complexity resource of a system of bosonic modes in Gaussian boson sampling.<n>We prove that the full problem compresses exactly onto the active symplectic sector that the dual program support generates.<n>Together these results establish that the program determines a canonical localized pure Gaussian component of the resource.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a rigorous analysis of the algebraic and geometric structure of the quantum complexity resource of a system of bosonic modes in Gaussian boson sampling. This resource underlies the quantum advantage of the system: its photon-counting statistics require the evaluation of a hafnian of the resource covariance matrix, and that computation is #P-hard. The resource covariance matrix is the solution of a semidefinite program that extracts the minimum-trace physical quantum part of the total covariance matrix; the complementary part is positive semidefinite and can therefore be simulated classically. Earlier work characterized this resource only through the trace of the quantum part, equal to its photon number. We characterize the optimizer itself, as a quantum state and as a geometric object, beyond the scalar given by its trace. We prove that it is a unique pure Gaussian state and construct an explicit oracle map, obeying an algebraic Riccati identity, that reconstructs the resource. We prove that the full problem compresses exactly onto the active symplectic sector that the dual program support generates. The passive-diagonalizable states are solved in closed form, the first explicit solvable class, and the whole program is shown to be equivalent to a minimization over the symplectic group, that is, over the Siegel upper half-space. Together these results establish that the program determines a canonical localized pure Gaussian component of the resource, and they provide the structural foundation for its detailed analysis.

Related papers

• Computable measures of fermionic non-Gaussianity from the covariance matrix [0.005748392537700255]
  We develop a convex resource theory of fermionic non-Gaussianity and introduce two families of computable measures for pure fermionic states.<n>We analyze both families for stabilizer and translation-invariant states, where they simplify and reveal additional structure.<n>Our work establishes a resource-theoretic framework for computable fermionic non-Gaussianity that unifies notions arising across quantum information, condensed-matter physics, and quantum chemistry.
  arXiv  Detail & Related papers  (2026-07-02T14:38:25Z)
• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  randomized quantum algorithms have been proposed in the context of quantum simulation and quantum linear algebra.<n>We provide explicit bounds on all relevant parameters that control the total error for a randomized quantum linear systems solver.<n>Our work serves as a bridge between theoretical algorithmic proposals and efficient hardware implementations.
  arXiv  Detail & Related papers  (2025-10-15T17:12:55Z)
• Efficient Preparation of Resource States for Hamiltonian Simulation and Universal Quantum Computation [0.3541849852479175]
  We extend previous studies on algorithm-tailored graph states to periodic sequences of generalized Pauli rotations.<n>We derive a novel scheme for the preparation of resource states based on a graph state and a ladder of CNOT gates.<n>We also deploy our two approaches to derive universal resource states from minimal universal sets of generating Hamiltonians.
  arXiv  Detail & Related papers  (2025-09-05T18:00:00Z)
• The symplectic rank of non-Gaussian quantum states [0.0]
  Non-Gaussianity is a key resource for achieving quantum advantages in bosonic platforms.<n>Here, we investigate the symplectic rank: a novel non-Gaussianity monotone that satisfies remarkable operational and resource-theoretic properties.<n>We show that the symplectic rank is a robust non-Gaussian measure, explaining how to witness it in experiments and how to exploit it to meaningfully benchmark different bosonic platforms.
  arXiv  Detail & Related papers  (2025-04-27T18:00:31Z)
• Efficient Representation of Gaussian Fermionic Pure States in Non-Computational Bases [0.0]
  This paper introduces an innovative approach for representing Gaussian fermionic states, pivotal in quantum spin systems and fermionic models. We focus on transitioning these states from the conventional computational (sigmaz) basis to more complex bases, such as (phi, fracpi2, alpha) We present a novel algorithm that not only simplifies the basis transformation but also reduces computational complexity.
  arXiv  Detail & Related papers  (2024-03-05T19:43:33Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• Quantum tomography of helicity states for general scattering processes [55.2480439325792]
  Quantum tomography has become an indispensable tool in order to compute the density matrix $rho$ of quantum systems in Physics. We present the theoretical framework for reconstructing the helicity quantum initial state of a general scattering process.
  arXiv  Detail & Related papers  (2023-10-16T21:23:42Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• The vacuum provides quantum advantage to otherwise simulatable architectures [49.1574468325115]
  We consider a computational model composed of ideal Gottesman-Kitaev-Preskill stabilizer states. We provide an algorithm to calculate the probability density function of the measurement outcomes.
  arXiv  Detail & Related papers  (2022-05-19T18:03:17Z)
• Classical shadows with Pauli-invariant unitary ensembles [0.0]
  We consider the class of Pauli-invariant unitary ensembles that are invariant under multiplication by a Pauli operator. Our results pave the way for more efficient or robust protocols for predicting important properties of quantum states.
  arXiv  Detail & Related papers  (2022-02-07T15:06:30Z)
• Local optimization on pure Gaussian state manifolds [63.76263875368856]
  We exploit insights into the geometry of bosonic and fermionic Gaussian states to develop an efficient local optimization algorithm. The method is based on notions of descent gradient attuned to the local geometry. We use the presented methods to collect numerical and analytical evidence for the conjecture that Gaussian purifications are sufficient to compute the entanglement of purification of arbitrary mixed Gaussian states.
  arXiv  Detail & Related papers  (2020-09-24T18:00:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.