Quantum Hamiltonian Certification

• URL: http://arxiv.org/abs/2505.13217v1
• Date: Mon, 19 May 2025 15:00:58 GMT
• Title: Quantum Hamiltonian Certification
• Authors: Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, Qi Zhao,
• Abstract summary: This work introduces a direct and efficient framework for Hamiltonian certification.<n>We show that the certification problem with respect to normalized Schatten $inftyco-norm is $mathco-norm, and therefore unlikely to have efficient solutions.<n>To enhance practical applicability, we develop an ancilla-free certification method that maintains the inverse precision scaling while eliminating the need for auxiliary qubits.
• Score: 12.536652791069576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We formalize and study the Hamiltonian certification problem. Given access to $e^{-\mathrm{i} Ht}$ for an unknown Hamiltonian $H$, the goal of the problem is to determine whether $H$ is $\varepsilon_1$-close to or $\varepsilon_2$-far from a target Hamiltonian $H_0$. While Hamiltonian learning methods have been extensively studied, they often require restrictive assumptions and suffer from inefficiencies when adapted for certification tasks. This work introduces a direct and efficient framework for Hamiltonian certification. Our approach achieves \textit{optimal} total evolution time $\Theta((\varepsilon_2-\varepsilon_1)^{-1})$ for certification under the normalized Frobenius norm, without prior structural assumptions. This approach also extends to certify Hamiltonians with respect to all Pauli norms and normalized Schatten $p$-norms for $1\leq p\leq2$ in the one-sided error setting ($\varepsilon_1=0$). Notably, the result in Pauli $1$-norm suggests a quadratic advantage of our approach over all possible Hamiltonian learning approaches. We also establish matching lower bounds to show the optimality of our approach across all the above norms. We complement our result by showing that the certification problem with respect to normalized Schatten $\infty$-norm is $\mathsf{coQMA}$-hard, and therefore unlikely to have efficient solutions. This hardness result provides strong evidence that our focus on the above metrics is not merely a technical choice but a requirement for efficient certification. To enhance practical applicability, we develop an ancilla-free certification method that maintains the inverse precision scaling while eliminating the need for auxiliary qubits, making our approach immediately accessible for near-term quantum devices with limited resources.

Related papers

• Optimal certification of constant-local Hamiltonians [3.2268950104324965]
  We study the problem of certifying local Hamiltonians from real-time access to their dynamics oracle.<n>We introduce the first intolerant Hamiltonian certification protocol that achieves optimal performance for all constant-locality Hamiltonians.
  arXiv  Detail & Related papers  (2025-12-10T15:58:05Z)
• Gaussian Certified Unlearning in High Dimensions: A Hypothesis Testing Approach [11.591273159662256]
  We introduce $varepsilon$-Gaussian certifiability, a canonical and robust notion well-suited to high-dimensional regimes.<n>We theoretically analyze the performance of a widely used unlearning algorithm based on one step of the Newton method.
  arXiv  Detail & Related papers  (2025-10-15T02:28:12Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Certifying and learning quantum Ising Hamiltonians [5.034708496440794]
  We show that certifying an Ising Hamiltonian in normalized Frobenius norm requires only $widetilde O (1/varepsilon)$ time evolution.<n>We design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters.<n>We extend our results on learning and certification of Gibbs states to general $k$-local Hamiltonians for any constant $k$
  arXiv  Detail & Related papers  (2025-09-12T13:33:20Z)
• Learning $k$-body Hamiltonians via compressed sensing [0.5867838258848337]
  We study the problem of learning a $k$-body Hamiltonian with $M$ unknown Pauli terms that are not necessarily geometrically local.<n>We propose a protocol that learns the Hamiltonian to precision $epsilon$ with total evolution time.
  arXiv  Detail & Related papers  (2024-10-24T17:16:19Z)
• 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.<n>Our algorithm recovers the Hamiltonian to $varepsilon$ error with total evolution time $O(log (n)/varepsilon)$, and has the following appealing properties.<n>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)
• Simple algorithms to test and learn local Hamiltonians [0.0]
  We consider the problems of testing and learning an $n$-qubit $k$-local Hamiltonian from queries to its evolution operator. For learning up to error $epsilon$, we show that $exp(O(k2+klog(1/epsilon))$ queries suffice.
  arXiv  Detail & Related papers  (2024-04-09T13:08:28Z)
• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  We give a complexity-time quantum algorithm for solving the ground states of a class of classically hard Hamiltonians. We show that the Hamiltonians that can be efficiently solved by our algorithms contain classically hard instances.
  arXiv  Detail & Related papers  (2024-01-25T05:01:02Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  We present a method for solving general non-strongly-concave bilevel optimization problems. Our results also improve upon the existing complexity for finding second-order stationary points in non-strongly-concave problems.
  arXiv  Detail & Related papers  (2023-06-30T20:36:44Z)
• Exponentially improved efficient machine learning for quantum many-body states with provable guarantees [0.0]
  We provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications. Our results provide theoretical guarantees for efficient learning of quantum many-body states and their properties, with model-independent applications.
  arXiv  Detail & Related papers  (2023-04-10T02:22:36Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  Unitarity estimation is a basic and important problem in quantum device certification and benchmarking. We provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms. We show that both the $d$-dependence and $epsilon$-dependence of our algorithms are optimal.
  arXiv  Detail & Related papers  (2022-12-19T09:36:33Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Learning many-body Hamiltonians with Heisenberg-limited scaling [3.460138063155115]
  We propose the first algorithm to achieve the Heisenberg limit for learning interacting $N$-qubit local Hamiltonian. After a total evolution time of $mathcalO(epsilon-1)$, the proposed algorithm can efficiently estimate any parameter in the $N$-qubit Hamiltonian to $epsilon$-error with high probability.
  arXiv  Detail & Related papers  (2022-10-06T16:30:51Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  A VI involves finding $xstar in mathcalX$ such that $langle F(x), x - xstarrangle geq 0$ for all $x in mathcalX$. We propose a $pth$-order method that does textitnot require any line search procedure and provably converges to a weak solution at a rate of $O(epsilon-2/(p+1))$.
  arXiv  Detail & Related papers  (2022-05-06T13:29:14Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

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.