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.
Consider a Hermitian operator A acting on a complex Hilbert space of dimension 2n. 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 ∣⟨ψ∣A∣ψ⟩∣ over a small collection Xn of product states ∣ψ⟩∈(C2)⊗n. More precisely, we show that whenever A is d-local, \textit{i.e.,} °(A)≤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 Xn 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.
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.
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σ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 ε1 -close to k -local or ε2 -far from k -local in the ℓ2 norm of the coefficients, with 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 -close to being s -sparse or ε2 -far from being s -sparse in the ℓ2 norm of the coefficients, with O(s6/(ε22−ε12)6) queries. Learning : We give a protocol to ε -learn unstructured Hamiltonian in the ℓ∞ norm of the coefficients with O(1/ε4) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in ℓ2 norm of the coefficients that only uses O(exp(k2+klog(1/ε))) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the ℓ2 norm with 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 (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 norm using 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 -close to being s -sparse or ε2 -far under the diamond norm, using 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), defined via the operator norm ∥A∥∞=σmax(A), given 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 poly(n) time. Since the operator norm distance T∞(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance 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(ρ), which can be exp(n) in general.
2. For general quantum states, we also provide a quantum estimator using O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP-complete and improves the 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 ∣ψ⟩ has overlap at least 1/2 with the top unit eigenvector of ∣ψ⟩⟨ψ∣−ρ, 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.