Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems

• URL: http://arxiv.org/abs/2510.01563v2
• Date: Sun, 09 Nov 2025 09:17:28 GMT
• Title: Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems
• Authors: Taehee Ko, Sungbin Lim,
• Abstract summary: We study the problems of state preparation, ground state preparation and quantum state preparation.<n>We propose an analytic approach to a quantum algorithm which prepares the ground state for $n$qubit Hamiltonian that is represented by $textpoly(n)$ Pauli operators.
• Score: 5.458506740538826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problems of state preparation, ground state preparation and quantum state preparation. We propose an analytic approach to a stochastic quantum algorithm which prepares the ground state for $n$-qubit Hamiltonian that is represented by $\text{poly}(n)$ Pauli operators and has an inverse-polynomial gap, requiring only $\text{poly}(n)$ Pauli rotations, measurements, and classical time complexity when $n$ exceeds a threshold, to inverse-polynomial precision given the initial overlap being lower bounded by $\frac{1}{2^n}$. Extending this result, we prove that any $n$-qubit quantum state can be prepared in two regimes: (1) with a constant number of Pauli rotations to constant precision, or (2) with a polynomial number of rotations to inverse-polynomial precision. Our results improve over previous approaches to quantum state preparation in terms of gate complexity, thereby yielding quantum space advantage. As an application, we identify a practical condition under which quadratic unconstrained binary optimization (QUBO) problems can be solved with exponential quantum speedups.

Related papers

• Universal initial state preparation for first quantized quantum simulations [1.6089851562703383]
  Preparation of symmetry-adapted initial states is a principal bottleneck in first-quantized quantum simulation.<n>We present a universal approach that efficiently maps any-size superposition of occupation-number configurations to the first bijquantized representation on a digital quantum computer.
  arXiv  Detail & Related papers  (2025-10-08T17:41:08Z)
• Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices [6.701793676773711]
  A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $mathrmTr(rhok O)$.<n>We present a quadratic quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods.<n>Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information.
  arXiv  Detail & Related papers  (2025-09-01T15:56:49Z)
• Topological control of quantum speed limits [55.2480439325792]
  We show that even if the quantum state is completely dispersionless, QFI in this state remains momentum-resolved.<n>We find bounds on quantum speed limit which scales as $sqrt|C|$ in a (dispersionless) topological phase.
  arXiv  Detail & Related papers  (2025-07-21T18:00:07Z)
• Quantum state preparation with polynomial resources: Branched-Subspaces Adiabatic Preparation (B-SAP) [0.0]
  We introduce a hybrid algorithm that integrates the conceptual strengths of Variational Quantum Algorithms (VQAs) and Adiabatic Preparation (AP)<n>Our approach is validated on the one-dimensional XYZ Heisenberg model with periodic boundary conditions across a broad parameters range and system sizes.<n>These results highlight the accuracy, efficiency, and robustness of the proposed algorithm, which offers a compelling pathway for the actual preparation of targeted quantum states on near-term quantum devices.
  arXiv  Detail & Related papers  (2025-05-19T20:26:35Z)
• Exponential quantum speedups in quantum chemistry with linear depth [0.0]
  We prove a connection to particle number conserving matchgate circuits with fermionic magic state inputs.<n>We apply this result to quantum multi-reference methods designed for near-term hardware.<n>We discuss the implications for achieving exponential quantum advantage in quantum chemistry on near-term hardware.
  arXiv  Detail & Related papers  (2025-03-26T23:15:32Z)
• 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)
• Sample-Efficient Estimation of Nonlinear Quantum State Functions [5.641998714611475]
  We introduce the quantum state function (QSF) framework by extending the SWAP test via linear combination of unitaries and parameterized quantum circuits.<n>Our framework enables the implementation of arbitrarily normalized degree-$n$ functions of quantum states with precision.<n>We apply QSF for developing quantum algorithms for fundamental tasks, including entropy, fidelity, and eigenvalue estimations.
  arXiv  Detail & Related papers  (2024-12-02T16:40:17Z)
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$ [8.264300525515097]
  Quantum signal processing and quantum value transformation are powerful tools to implement transformations of block-encoded matrices on quantum computers. We propose a framework which realizes multiples simultaneously from a block-encoded input. We also give an algorithm to construct the quantum circuit that gives the desired transformation.
  arXiv  Detail & Related papers  (2024-07-19T14:15:20Z)
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
  Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve quantum advantages. We present a novel $gammaPPP method based on the integral path of observables back-propagation on paths. We conduct classical simulations of IBM's zeronoised experimental results on the 127-qubit Eagle processor.
  arXiv  Detail & Related papers  (2023-06-09T10:42:07Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices [3.1952399274829775]
  We develop a tool called quantum eigenvalue transformation of unitary matrices with reals (QET-U) This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model.
  arXiv  Detail & Related papers  (2022-04-12T17:11:40Z)
• Escaping from the Barren Plateau via Gaussian Initializations in Deep Variational Quantum Circuits [63.83649593474856]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years.<n>However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number.<n>This result leads to a general standpoint that deep quantum circuits would not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Pseudo-dimension of quantum circuits [0.0]
  We prove pseudo-dimension bounds on the output probability of quantum circuits. We show that circuits of known size and depth are PAC-learnable.
  arXiv  Detail & Related papers  (2020-02-04T19:00:13Z)

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.