Hardness of classically sampling quantum chemistry circuits

• URL: http://arxiv.org/abs/2504.12893v1
• Date: Thu, 17 Apr 2025 12:34:33 GMT
• Title: Hardness of classically sampling quantum chemistry circuits
• Authors: Ayoub Hafid, Hokuto Iwakiri, Kento Tsubouchi, Nobuyuki Yoshioka, Masaya Kohda,
• Abstract summary: We extend the scope to address quantum advantage in tasks relevant to chemistry and physics.<n>We show that a class of unitary cluster Jastrow (UCJ) ansatz can be used to perform arbitrary quantum-time computations.<n>Our demonstration, worst-case nonsimbility of UCJ, would potentially imply quantum advantage in quantum algorithms for chemistry and physics.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Significant advances have been made in the study of quantum advantage both in theory and experiment, although these have mostly been limited to artificial setups. In this work, we extend the scope to address quantum advantage in tasks relevant to chemistry and physics. Specifically, we consider the unitary cluster Jastrow (UCJ) ansatz-a variant of the unitary coupled cluster ansatz, which is widely used to solve the electronic structure problem on quantum computers-to show that sampling from the output distributions of quantum circuits implementing the UCJ ansatz is likely to be classically hard. More specifically, we show that there exist UCJ circuits for which classical simulation of sampling cannot be performed in polynomial time, under a reasonable complexity-theoretical assumption that the polynomial hierarchy does not collapse. Our main contribution is to show that a class of UCJ circuits can be used to perform arbitrary instantaneous quantum polynomial-time (IQP) computations, which are already known to be classically hard to simulate under the same complexity assumption. As a side result, we also show that UCJ equipped with post-selection can generate the class post-BQP. Our demonstration, worst-case nonsimulatability of UCJ, would potentially imply quantum advantage in quantum algorithms for chemistry and physics using unitary coupled cluster type ansatzes, such as the variational quantum eigensolver and quantum-selected configuration interaction.

Related papers

• Simulating quantum circuits with restricted quantum computers [0.0]
  This thesis is dedicated to the simulation of nonlocal quantum computation using local quantum operations.<n>We characterize the optimal simulation overhead for a broad range of practically relevant nonlocal states and channels.<n>We also investigate the utility of classical communication between the local parties.
  arXiv  Detail & Related papers  (2025-03-27T17:59:45Z)
• Exposing a Fatal Flaw in Sample-based Quantum Diagonalization Methods [0.0]
  We show that QSCI methods face fundamental limitations that severely hinder their practical applicability in chemistry.<n>We demonstrate that while QSCI can, in principle, yield high-quality CI expansions, the method struggles with inefficiencies in finding new determinants.<n>This ultimately hinders utility in quantum chemistry applications as QSCI falls behind more efficient classical counterparts.
  arXiv  Detail & Related papers  (2025-01-13T11:30:43Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
  We present a model for parallelizing simulation of quantum circuit executions. The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
  arXiv  Detail & Related papers  (2024-06-05T17:16:07Z)
• Quantum computation of conical intersections on a programmable superconducting quantum processor [10.064448021157139]
  Conical intersections (CIs) are pivotal in many photochemical processes. We present the first successful realization of a hybrid quantum-classical state-average complete active space self-consistent method.
  arXiv  Detail & Related papers  (2024-02-20T04:12:40Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Protocols for classically training quantum generative models on probability distributions [17.857341127079305]
  Quantum Generative Modelling (QGM) relies on preparing quantum states and generating samples as hidden - or known - probability distributions. We propose protocols for classical training of QGMs based on circuits of the specific type that admit an efficient gradient. We numerically demonstrate the end-to-end training of IQP circuits using probability distributions for up to 30 qubits on a regular desktop computer.
  arXiv  Detail & Related papers  (2022-10-24T17:57:09Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Chaos in coupled Kerr-nonlinear parametric oscillators [0.0]
  We investigate complex dynamics, i.e., chaos, in two coupled nondissipative KPOs at a few-photon level. We conclude that some of them can be regarded as quantum signatures of chaos, together with energy-level spacing statistics.
  arXiv  Detail & Related papers  (2021-10-08T10:35:12Z)
• Preparing random states and benchmarking with many-body quantum chaos [48.044162981804526]
  We show how to predict and experimentally observe the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics. The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system. Our work has implications for understanding randomness in quantum dynamics, and enables applications of this concept in a wider context.
  arXiv  Detail & Related papers  (2021-03-05T08:32:43Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond [46.39654665163597]
  We report on experimental tests of topological defect formation via the one-dimensional transverse-field Ising model. We find that the quantum simulator results can indeed be explained by the KZM for open-system quantum dynamics with phase-flip errors. This implies that the theoretical predictions of the generalized KZM theory, which assumes isolation from the environment, applies beyond its original scope to an open system.
  arXiv  Detail & Related papers  (2020-01-31T02:55:35Z)

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.