Algorithmic Cluster Expansions for Quantum Problems

• URL: http://arxiv.org/abs/2306.08974v2
• Date: Tue, 16 Jan 2024 23:38:03 GMT
• Title: Algorithmic Cluster Expansions for Quantum Problems
• Authors: Ryan L. Mann, Romy M. Minko
• Abstract summary: We establish a general framework for developing approximation algorithms for a class of counting problems. We apply our framework to approximating probability amplitudes of a class of quantum circuits close to the identity. We show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of abstract polymer models formalism of Koteck\'y and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.

Related papers

• Estimating quantum amplitudes can be exponentially improved [11.282486674587236]
  Estimating quantum amplitudes is a fundamental task in quantum computing. We present a novel framework for estimating quantum amplitudes by transforming pure states into their matrix forms. Our framework achieves the standard quantum limit $epsilon-2$ and the Heisenberg limit $epsilon-1$, respectively.
  arXiv  Detail & Related papers  (2024-08-25T04:35:53Z)
• 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)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm [0.0]
  Two-stage optimization involves calculating the expected cost of future decisions to inform the best decision in the present. We provide a quantum algorithm to estimate the expected value function in a two-stage optimization problem in time largely independent from the complexity of the random variable.
  arXiv  Detail & Related papers  (2024-02-23T00:07:34Z)
• Mixed State Variational Quantum Eigensolver for the Estimation of Expectation Values at Finite Temperature [0.0]
  We introduce a novel hybrid quantum-classical algorithm for the near-term computation of expectation values in quantum systems at finite temperatures. This is based on two stages: on the first one, a mixed state approximating a fiducial truncated density matrix is prepared through Variational Quantum Eigensolving (VQE) techniques. This is then followed by a reweighting stage where the expectation values for observables of interest are computed.
  arXiv  Detail & Related papers  (2024-01-30T17:29:58Z)
• A Universal Quantum Algorithm for Weighted Maximum Cut and Ising Problems [0.0]
  We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system.
  arXiv  Detail & Related papers  (2023-06-10T23:28:13Z)
• Quantum Thermal State Preparation [39.91303506884272]
  We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations. We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
  arXiv  Detail & Related papers  (2023-03-31T17:29:56Z)
• 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)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature [0.0]
  We establish an efficient approximation algorithm for the partition functions of a class of quantum spin systems at low temperature. Our algorithm is based on combining the contour representation of quantum spin systems of this type due to Borgs, Koteck'y, and Ueltschi.
  arXiv  Detail & Related papers  (2022-01-17T17:27:13Z)
• 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)

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.