DQC1-hardness of estimating correlation functions

• URL: http://arxiv.org/abs/2411.05208v1
• Date: Thu, 07 Nov 2024 22:12:25 GMT
• Title: DQC1-hardness of estimating correlation functions
• Authors: Subhayan Roy Moulik, Sergii Strelchuk,
• Abstract summary: Out-of-Time-Order Correlation function measures transport properties of dynamical systems. We characterise the computational complexity of estimating OTOCs over all eigenstates. We show it is Complete for the One Clean Qubit model (DQC1)
• Score: 0.0
• License:
• Abstract: Out-of-Time-Order Correlation function measures transport properties of dynamical systems. They are ubiquitously used to measure quantum mechanical quantities, such as scrambling times, criticality in phase transitions, and detect onset of thermalisation. We characterise the computational complexity of estimating OTOCs over all eigenstates and show it is Complete for the One Clean Qubit model (DQC1). We then generalise our setup to establish DQC1-Completeness of N-time Correlation functions over all eigenstates. Building on previous results, the DQC1-Completeness of OTOCs and N-time Correlation functions then allows us to highlight a dichotomy between query complexity and circuit complexity of estimating correlation functions.

Related papers

• Spectroscopy and complex-time correlations using minimally entangled typical thermal states [39.58317527488534]
  We introduce a practical approach to computing such correlators using minimally entangled typical thermal states. We show that these numerical techniques capture the finite-temperature dynamics of the Shastry-Sutherland model.
  arXiv  Detail & Related papers  (2024-05-28T18:00:06Z)
• Complexity in two-point measurement schemes [0.0]
  We show that the probability distribution associated with the change of an observable in a two-point measurement protocol with a perturbation can be written as an auto-correlation function. We probe how the evolved state spreads in the corresponding conjugate space. We show that the complexity saturates for large values of the parameter only when the pre-quench Hamiltonian is chaotic.
  arXiv  Detail & Related papers  (2023-11-14T04:00:31Z)
• Continuous-time convolutions model of event sequences [46.3471121117337]
  Event sequences are non-uniform and sparse, making traditional models unsuitable. We propose COTIC, a method based on an efficient convolution neural network designed to handle the non-uniform occurrence of events over time. COTIC outperforms existing models in predicting the next event time and type, achieving an average rank of 1.5 compared to 3.714 for the nearest competitor.
  arXiv  Detail & Related papers  (2023-02-13T10:34:51Z)
• Sample Complexity of Kernel-Based Q-Learning [11.32718794195643]
  We propose a non-parametric Q-learning algorithm which finds an $epsilon$-optimal policy in an arbitrarily large scale discounted MDP. To the best of our knowledge, this is the first result showing a finite sample complexity under such a general model.
  arXiv  Detail & Related papers  (2023-02-01T19:46:25Z)
• Grouped self-attention mechanism for a memory-efficient Transformer [64.0125322353281]
  Real-world tasks such as forecasting weather, electricity consumption, and stock market involve predicting data that vary over time. Time-series data are generally recorded over a long period of observation with long sequences owing to their periodic characteristics and long-range dependencies over time. We propose two novel modules, Grouped Self-Attention (GSA) and Compressed Cross-Attention (CCA) Our proposed model efficiently exhibited reduced computational complexity and performance comparable to or better than existing methods.
  arXiv  Detail & Related papers  (2022-10-02T06:58:49Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Minimally Entangled Typical Thermal States Algorithms for Finite Temperature Matsubara Green Functions [0.0]
  We extend finite-temperature tensor network methods to compute Matsubara imaginary-time correlation functions. As a benchmark, we study the single-band Anderson impurity model. Results are competitive with state-of-the-art continuous time Monte Carlo.
  arXiv  Detail & Related papers  (2021-07-29T13:02:25Z)
• Observation of Time-Crystalline Eigenstate Order on a Quantum Processor [80.17270167652622]
  Quantum-body systems display rich phase structure in their low-temperature equilibrium states. We experimentally observe an eigenstate-ordered DTC on superconducting qubits. Results establish a scalable approach to study non-equilibrium phases of matter on current quantum processors.
  arXiv  Detail & Related papers  (2021-07-28T18:00:03Z)
• Quantum-Classical Hybrid Algorithm for the Simulation of All-Electron Correlation [58.720142291102135]
  We present a novel hybrid-classical algorithm that computes a molecule's all-electron energy and properties on the classical computer. We demonstrate the ability of the quantum-classical hybrid algorithms to achieve chemically relevant results and accuracy on currently available quantum computers.
  arXiv  Detail & Related papers  (2021-06-22T18:00:00Z)
• Out-of-time-order correlations and the fine structure of eigenstate thermalisation [58.720142291102135]
  Out-of-time-orderors (OTOCs) have become established as a tool to characterise quantum information dynamics and thermalisation. We show explicitly that the OTOC is indeed a precise tool to explore the fine details of the Eigenstate Thermalisation Hypothesis (ETH) We provide an estimation of the finite-size scaling of $omega_textrmGOE$ for the general class of observables composed of sums of local operators in the infinite-temperature regime.
  arXiv  Detail & Related papers  (2021-03-01T17:51:46Z)

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.