Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.11979

Approximating the operator norm of local Hamiltonians via few quantum states

Becker, Lars, Joseph Slote, Alexander L'vovich Vol'berg, Haonan Zhang

Published Sep 15, 2025• 2 citations
arXivHTMLPDF

Abstract

Consider a Hermitian operator $A$ acting on a complex Hilbert space of dimension $2^n$. We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian, its operator norm can be approximated independently of $n$ by maximizing $|\braket{ψ|A|ψ}|$ over a small collection $\mathbf{X}_n$ of product states $\ketψ\in (\mathbf{C}^{2})^{\otimes n}$. More precisely, we show that whenever $A$ is $d$-local, \textit{i.e.,} $°(A)\le d$, we have the following discretization-type inequality: \[ \|A\|\le C(d)\max_{ψ\in \mathbf{X}_n}|\braket{ψ|A|ψ}|. \] The constant $C(d)$ depends only on $d$. This collection $\mathbf{X}_n$ of $ψ$'s, termed a \emph{quantum norm design}, is independent of $A$, and consists of product states, and can have cardinality as small as $(1+\eps)^n$, which is essentially tight. Previously, norm designs were known only for homogeneous $d$-localHamiltonians $A$ \cite{L,BGKT,ACKK}, and for non-homogeneous $2$-local traceless $A$ \cite{BGKT}. Several other results, such as boundedness of Rademacher projections for all levels and estimates of operator norms of random Hamiltonians, are also given.

DOI
10.48550/arxiv.2509.11979

Related papers

Tightness of and counterexamples to several quantum estimates

Joseph Slote, Alexander L'vovich Vol'berg, Haonan Zhang

We prove here several tightness results for such quantum inequalities as 1) the comparison of operator norm and product norm of $d$-local hamiltonians, 2) Bohnenblust--Hille inequality for $d$-local hamiltonians, 3) for quantum Fourier entropy-influence conjecture. We give a deterministic prove of the sharpness of Bohnenblust--Hille exponent. We also discuss the quantum Aaronson--Ambainis conjecture in a special case of anti-commuting Pauli strings.

arXiv:2608.04411•Aug 5, 2026•2 citations

Product-state Approximations to Quantum Ground States

Fernando G. S. L. Brandão, Aram W. Harrow

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum gen-eralization of constraint satisfaction problems (CSPs) and has a central role both in quantum many-body physics and quantum complexity theory. A key feature that distinguishes quan-tum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error. First, we show the existence of a good product-state approximation for the ground-state en-ergy of 2-local Hamiltonians with one or more of the following properties: (1) high degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some parti-tion into small pieces. The approximation based on degree is a surprising difference between quantum Hamiltonians and classical CSPs, since in the classical setting, higher degree is usu-ally associated with harder CSPs. The approximation based on low entanglement, in turn, was

•Jun 1, 2013•45 citations

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an n -qubit Hamiltonian \(H=\sum _x \lambda _x \sigma _x\) expressed in its Pauli basis, from queries to its evolution operator \(U=e^{-iHt}\) . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is \(\varepsilon _1\) -close to k -local or \(\varepsilon _2\) -far from k -local in the \(\ell _2\) norm of the coefficients, with \(O(1/(\varepsilon _2-\varepsilon _1)^{4})\) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is \(\varepsilon _1\) -close to being s -sparse or \(\varepsilon _2\) -far from being s -sparse in the \(\ell _2\) norm of the coefficients, with \(O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})\) queries. Learning : We give a protocol to \(\varepsilon \) -learn unstructured Hamiltonian in the \(\ell _\infty \) norm of the coefficients with \(O(1/\varepsilon ^4)\) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in \(\ell _2\) norm of the coefficients that only uses \(O(\exp (k^2+k\log (1/\varepsilon )))\) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the \(\ell _2\) norm with \(O(s^2/\varepsilon ^4)\) queries. Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; squaring the query complexity and paying a \((\log n)\) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the \(\ell _2\) norm using \(\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})\) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being \(\varepsilon _1\) -close to being s -sparse or \(\varepsilon _2\) -far under the diamond norm, using \(\tilde{O}(s^2/(\varepsilon _2-\varepsilon _1)^6)\) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge of the support of the Hamiltonian.

Communications in Mathematical Physics•Dec 8, 2025•2 citations

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm poly}(n)$-size state-preparation circuits of $n$-qubit quantum states $ρ_0$ and $ρ_1$. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using $Θ(1/ε)$ queries to the state-preparation circuits. Consequently, for constant additive error, say $ε=1/5$, our estimator runs in ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf QMA}$ upper bound sketched by Liu and Wang (ESA 2025). Together with an $Ω(1/ε)$ quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905•Leibniz international proceedings in informatics•Jul 7, 2026•1 citation

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an unknown n -qubit quantum Hamiltonian H =∑ x λ x σ x expressed in its Pauli basis, from queries to its evolution operator e − iHt under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only k -local terms or has sparsity at most s : (1) Local Hamiltonians : We give a tolerant testing protocol to decide if a Hamiltonian is ε 1 -close to k -local or ε 2 -far from k -local, with O (1/(ε 2 −ε 1 ) 4 ) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO’24]. For learning a k -local Hamiltonian up to error ε, we give a protocol with query complexity and total time evolution exp( O ( k 2 + k log(1/ε))). Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of n . (2) Sparse Hamiltonians : We give a protocol for testing whether a Hamiltonian is ε 1 -close to being s -sparse or ε 2 -far from being s -sparse, with O ( s 6 /(ε 2 2 −ε 1 2 ) 6 ) queries. For learning up to error ε, we show that O ( s 4 /ε 8 ) queries suffices. (3) Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; increasing the query complexity by a (log n )-factor in the local case and an n -factor in the sparse case. (4) Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians using Õ( s 14 /(ε 2 2 −ε 1 2 ) 18 ) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε 1 -close to being s -sparse or ε 2 -far under the diamond norm, using Õ( s 2 /(ε 2 −ε 1 ) 6 ) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge about the support of the Hamiltonian terms.

arXiv:2411.00082•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•21 citations

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Hallgren, Sean, Lee, Eunou, Ojas Parekh

We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.

Leibniz international proceedings in informatics•Jan 1, 2020•7 citations
Consider a Hermitian operator AAA acting on a complex Hilbert space of dimension 2n2^n2n. We show that when AAA has small degree in the Pauli expansion, or in other words, AAA is a local nnn-qubit Hamiltonian, its operator norm can be approximated independently of nnn by maximizing ∣⟨ψ∣A∣ψ⟩∣|\braket{ψ|A|ψ}|∣⟨ψ∣A∣ψ⟩∣ over a small collection Xn\mathbf{X}_nXn​ of product states ∣ψ⟩∈(C2)⊗n\ketψ\in (\mathbf{C}^{2})^{\otimes n}∣ψ⟩∈(C2)⊗n. More precisely, we show that whenever AAA is ddd-local, \textit{i.e.,} °(A)≤d°(A)\le d°(A)≤d, we have the following discretization-type inequality: [ |A|\le C(d)\max_{ψ\in \mathbf{X}_n}|\braket{ψ|A|ψ}|. ] The constant C(d)C(d)C(d) depends only on ddd. This collection Xn\mathbf{X}_nXn​ of ψψψ's, termed a \emph{quantum norm design}, is independent of AAA, and consists of product states, and can have cardinality as small as (1+\eps)n(1+\eps)^n(1+\eps)n, which is essentially tight. Previously, norm designs were known only for homogeneous ddd-localHamiltonians AAA \cite{L,BGKT,ACKK}, and for non-homogeneous 222-local traceless AAA \cite{BGKT}. Several other results, such as boundedness of Rademacher projections for all levels and estimates of operator norms of random Hamiltonians, are also given.
We prove here several tightness results for such quantum inequalities as 1) the comparison of operator norm and product norm of ddd-local hamiltonians, 2) Bohnenblust--Hille inequality for ddd-local hamiltonians, 3) for quantum Fourier entropy-influence conjecture. We give a deterministic prove of the sharpness of Bohnenblust--Hille exponent. We also discuss the quantum Aaronson--Ambainis conjecture in a special case of anti-commuting Pauli strings.
The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum gen-eralization of constraint satisfaction problems (CSPs) and has a central role both in quantum many-body physics and quantum complexity theory. A key feature that distinguishes quan-tum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error. First, we show the existence of a good product-state approximation for the ground-state en-ergy of 2-local Hamiltonians with one or more of the following properties: (1) high degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some parti-tion into small pieces. The approximation based on degree is a surprising difference between quantum Hamiltonians and classical CSPs, since in the classical setting, higher degree is usu-ally associated with harder CSPs. The approximation based on low entanglement, in turn, was
We consider the problems of testing and learning an n -qubit Hamiltonian H=∑xλxσxH=\sum _x \lambda _x \sigma _xH=∑x​λx​σx​ expressed in its Pauli basis, from queries to its evolution operator U=e−iHtU=e^{-iHt}U=e−iHt . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is ε1\varepsilon _1ε1​ -close to k -local or ε2\varepsilon _2ε2​ -far from k -local in the ℓ2\ell _2ℓ2​ norm of the coefficients, with O(1/(ε2−ε1)4)O(1/(\varepsilon _2-\varepsilon _1)^{4})O(1/(ε2​−ε1​)4) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is ε1\varepsilon _1ε1​ -close to being s -sparse or ε2\varepsilon _2ε2​ -far from being s -sparse in the ℓ2\ell _2ℓ2​ norm of the coefficients, with O(s6/(ε22−ε12)6)O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})O(s6/(ε22​−ε12​)6) queries. Learning : We give a protocol to ε\varepsilon ε -learn unstructured Hamiltonian in the ℓ∞\ell _\infty ℓ∞​ norm of the coefficients with O(1/ε4)O(1/\varepsilon ^4)O(1/ε4) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in ℓ2\ell _2ℓ2​ norm of the coefficients that only uses O(exp⁡(k2+klog⁡(1/ε)))O(\exp (k^2+k\log (1/\varepsilon )))O(exp(k2+klog(1/ε))) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the ℓ2\ell _2ℓ2​ norm with O(s2/ε4)O(s^2/\varepsilon ^4)O(s2/ε4) queries. Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; squaring the query complexity and paying a (log⁡n)(\log n)(logn) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the ℓ2\ell _2ℓ2​ norm using O~(s14/(ε22−ε12)18)\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})O~(s14/(ε22​−ε12​)18) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε1\varepsilon _1ε1​ -close to being s -sparse or ε2\varepsilon _2ε2​ -far under the diamond norm, using O~(s2/(ε2−ε1)6)\tilde{O}(s^2/(\varepsilon _2-\varepsilon _1)^6)O~(s2/(ε2​−ε1​)6) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge of the support of the Hamiltonian.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1){\rm T}_{\infty}(ρ_0,ρ_1)T∞​(ρ0​,ρ1​), defined via the operator norm ∥A∥∞=σmax⁡(A)\|A\|_{\infty} = σ_{\max}(A)∥A∥∞​=σmax​(A), given poly(n){\rm poly}(n)poly(n)-size state-preparation circuits of nnn-qubit quantum states ρ0ρ_0ρ0​ and ρ1ρ_1ρ1​. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states: 1. When one state is pure, we establish an optimal quantum estimator using Θ(1/ε)Θ(1/ε)Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5ε=1/5ε=1/5, our estimator runs in poly(n){\rm poly}(n)poly(n) time. Since the operator norm distance T∞(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)T∞​(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}(|ψ\rangle\!\langleψ|,ρ)T(∣ψ⟩⟨ψ∣,ρ), our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with rank(ρ){\rm rank}(ρ)rank(ρ), which can be exp⁡(n)\exp(n)exp(n) in general. 2. For general quantum states, we also provide a quantum estimator using O~(1/ε3/2)\widetilde{O}(1/ε^{3/2})O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP{\sf BQP}BQP-complete and improves the QMA{\sf QMA}QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε)Ω(1/ε)Ω(1/ε) quantum query complexity lower bound, this leaves only square-root room for improvement. The key intuition behind our estimators is that, when one state is pure, the pure state ∣ψ⟩|ψ\rangle∣ψ⟩ has overlap at least 1/21/21/2 with the top unit eigenvector of ∣ψ⟩ ⁣⟨ψ∣−ρ|ψ\rangle\!\langleψ|-ρ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
We consider the problems of testing and learning an unknown n -qubit quantum Hamiltonian H =∑ x λ x σ x expressed in its Pauli basis, from queries to its evolution operator e − iHt under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only k -local terms or has sparsity at most s : (1) Local Hamiltonians : We give a tolerant testing protocol to decide if a Hamiltonian is ε 1 -close to k -local or ε 2 -far from k -local, with O (1/(ε 2 −ε 1 ) 4 ) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO’24]. For learning a k -local Hamiltonian up to error ε, we give a protocol with query complexity and total time evolution exp( O ( k 2 + k log(1/ε))). Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of n . (2) Sparse Hamiltonians : We give a protocol for testing whether a Hamiltonian is ε 1 -close to being s -sparse or ε 2 -far from being s -sparse, with O ( s 6 /(ε 2 2 −ε 1 2 ) 6 ) queries. For learning up to error ε, we show that O ( s 4 /ε 8 ) queries suffices. (3) Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; increasing the query complexity by a (log n )-factor in the local case and an n -factor in the sparse case. (4) Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians using Õ( s 14 /(ε 2 2 −ε 1 2 ) 18 ) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε 1 -close to being s -sparse or ε 2 -far under the diamond norm, using Õ( s 2 /(ε 2 −ε 1 ) 6 ) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge about the support of the Hamiltonian terms.
We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.