Hamiltonian Property Testing

• URL: http://arxiv.org/abs/2403.02968v2
• Date: Tue, 9 Apr 2024 06:07:17 GMT
• Title: Hamiltonian Property Testing
• Authors: Andreas Bluhm, Matthias C. Caro, Aadil Oufkir,
• Abstract summary: Locality is a fundamental feature of many physical time evolutions. No protocols to rigorously test whether an unknown Hamiltonian is local were known.
• Score: 0.8192907805418583
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown $n$-qubit Hamiltonian $H$ is $k$-local or $\varepsilon$-far from all $k$-local Hamiltonians, given access to the time evolution along $H$. First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require $\tilde{\Omega}(2^n)$ many time evolution queries and an expected total evolution time of $\tilde{\Omega}(2^n / \varepsilon)$, and even coherent testers need $\Omega(2^{n/2})$ many queries and $\Omega(2^{n/2}/\varepsilon)$ total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
  arXiv  Detail & Related papers  (2024-05-28T18:00:32Z)
• Structure learning of Hamiltonians from real-time evolution [22.397920564324973]
  We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area. Our algorithm recovers the Hamiltonian to $varepsilon$ error with total evolution time $O(log (n)/varepsilon)$, and has the following appealing properties. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy $varepsilon$ with total evolution time beating the standard limit of $1/varepsilon2$.
  arXiv  Detail & Related papers  (2024-04-30T18:00:00Z)
• Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States [0.6768558752130311]
  We introduce a new approach to learn Hamiltonians through a resource that we call the pseudo-Choi state. We show that for a Hamiltonian with $M$ terms the Hamiltonian coefficients can be estimated via classical shadow tomography within error. We also show that our learning process is robust to errors in the resource states and to errors in the Hamiltonian class.
  arXiv  Detail & Related papers  (2023-08-24T18:36:51Z)
• On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation [4.925967492198012]
  Hamiltonian simulation is one of the most important problems in the field of quantum computing. Existing simulation algorithms require running time at least linear in the evolution time $T$. It is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism.
  arXiv  Detail & Related papers  (2023-05-21T12:30:00Z)
• 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)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Hamiltonian simulation with random inputs [74.82351543483588]
  Theory of average-case performance of Hamiltonian simulation with random initial states. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models.
  arXiv  Detail & Related papers  (2021-11-08T19:08:42Z)
• Optimal parent Hamiltonians for time-dependent states [0.0]
  Given a generic time-dependent many-body quantum state, we determine the associated parent Hamiltonian. We find the optimal Hamiltonian once a set of realistic elementary interactions is defined.
  arXiv  Detail & Related papers  (2021-05-21T07:54:55Z)
• Variational quantum eigensolvers for sparse Hamiltonians [0.0]
  Hybrid quantum-classical variational algorithms such as the variational quantum eigensolver (VQE) are promising applications for noisy, intermediate-scale quantum computers. We extend VQE to general sparse Hamiltonians.
  arXiv  Detail & Related papers  (2020-12-13T22:36:51Z)

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.