Free Snacks in Quantum Complexity

• URL: http://arxiv.org/abs/2509.04618v1
• Date: Thu, 04 Sep 2025 19:02:53 GMT
• Title: Free Snacks in Quantum Complexity
• Authors: Gerard McCaul,
• Abstract summary: We analyse the recently developed Imaginary-Time Quantum Dynamical Emulation (ITQDE)<n>This method enables estimation of spectral densities, partition functions, and low-lying gaps.<n>We derive scaling and stability criteria that diagnose when its estimates are reliable.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating ground-state energies is a cornerstone problem in Hamiltonian complexity, and in general requires exponential resources even on quantum computers. It is in this context we analyse the recently developed Imaginary-Time Quantum Dynamical Emulation (ITQDE). This method enables estimation of spectral densities, partition functions, and low-lying gaps, but requires only minimal coherent control, modest classical post-processing, and no state preparation. Using a quadrature-based formulation, we derive scaling and stability criteria that diagnose when its estimates are reliable, and introduce a controlled smoothing that yields a principled bias-variance trade off. The resulting picture preserves the hardness of exact eigenvalue resolution but reveals a practical regime - a "free snack" - here coarse-grained spectral information is obtainable with only polynomial resources. By recasting sampling costs as explicit bounds on resolvable bandwidths, the intermediate regime between trivial and intractable complexity becomes accessible on near-term quantum hardware.

Related papers

• Optimal quantum learning in proximity to universality [0.0]
  boundary between classically simulable and computationally superior quantum systems is fundamental to identifying true quantum advantage.<n>We introduce a tunable $N$-qubit random circuit model, where a fraction $p$ of Clifford gates are probabilistically substituted with nonstabilizing conditional-$hatT$ gates.<n>We establish a direct correspondence between the reservoir's performance on temporal processing tasks and its entanglement spectrum statistics and long-range nonstabilizer resource content.
  arXiv  Detail & Related papers  (2025-10-21T13:27:41Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Near-Optimal Simultaneous Estimation of Quantum State Moments [7.1834855718325805]
  We introduce a framework for resource-efficient simultaneous estimation of quantum state moments via qubit reuse.<n>By leveraging qubit reset operations, our core circuit for simultaneous moment estimation requires only $2m+1$ physical qubits and $mathcalO(k)$ CSWAP gates.<n>We demonstrate this protocol's utility by showing that the estimated moments yield tight bounds on a state's maximum eigenvalue and present applications in quantum virtual cooling to access low-energy states of the Heisenberg model.
  arXiv  Detail & Related papers  (2025-09-29T14:23:26Z)
• Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound [0.2606834301724095]
  This paper introduces the Reference-Contingent Complexity (RCC), an information-theoretic measure calibrated by the available quantum operations.<n>Our central result is a key theorem that rigorously proves the RCC serves as a lower bound for the complexity of any universal quantum circuit.<n>This work provides a "ruler" for quantum technology that is structure-fair and enables cross-platform comparison.
  arXiv  Detail & Related papers  (2025-09-20T14:58:34Z)
• Detecting genuine non-Gaussian entanglement [0.0]
  Non-Gaussian entanglement is a central challenge for advancing quantum information processing, photonic quantum computing, and metrology.<n>Here, we put forward continuous-variable counterparts of the recently introduced entanglement criteria based on moments of the partially transposed state.<n>Our multicopy method enables the detection of genuine non-Gaussian entanglement for various relevant state families overlooked by standard approaches.
  arXiv  Detail & Related papers  (2025-04-22T12:22:30Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition.<n>We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Dissipation-induced Quantum Homogenization for Temporal Information Processing [44.99833362998488]
  Quantum reservoirs have great potential as they utilize the complex real-time dissipative dynamics of quantum systems for information processing and target time-series generation without precise control or fine-tuning of the Hamiltonian parameters.<n>We propose the disordered quantum homogenizer as an alternative platform, and prove it satisfies the necessary and sufficient conditions - stability and contractivity - of the reservoir dynamics.<n>The results indicate that the quantum homogenization protocol, physically implementable as either nuclear magnetic resonance ensemble or a photonic system, can potentially function as a reservoir computer.
  arXiv  Detail & Related papers  (2024-12-13T09:05:41Z)
• Disorder-Free Localization for Benchmarking Quantum Computers [0.0]
  We show how a canonical model of Disorder-free localization can be efficiently implemented on gate-based quantum computers. We show that the simultaneous observation of the absence of correlation spreading and tunable entanglement growth to a volume law provides an ideal testbed for benchmarking the capabilities of quantum computers.
  arXiv  Detail & Related papers  (2024-10-10T18:00:00Z)
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits [37.84307089310829]
  Variational quantum computing schemes train a loss function by sending an initial state through a parametrized quantum circuit. Despite their promise, the trainability of these algorithms is hindered by barren plateaus. We present a general Lie algebra that provides an exact expression for the variance of the loss function of sufficiently deep parametrized quantum circuits.
  arXiv  Detail & Related papers  (2023-09-17T18:14:10Z)
• A Universal Framework for Quantum Dissipation:Minimally Extended State Space and Exact Time-Local Dynamics [5.221249829454763]
  dynamics of open quantum systems is formulated in a minimally extended state space. Time-local evolution equation is created in a mixed Liouville-Fock space.
  arXiv  Detail & Related papers  (2023-07-31T15:57:10Z)
• Making ab initio QED functional(s): Non-perturbative and photon-free effective frameworks for strong light-matter coupling [0.0]
  We provide a non-perturbative photon-free formulation of quantum electrodynamics (QED) in the long-wavelength limit. We show how this formulation can be used to devise approximations for quantum-electrodynamical density-functional theory (QEDFT) This is the first QEDFT functional that accounts for the quantized nature of light.
  arXiv  Detail & Related papers  (2021-06-14T15:37:44Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)

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.