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:2608.04411

Tightness of and counterexamples to several quantum estimates

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

Published Aug 5, 2026• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2608.04411

Related papers

Approximating the operator norm of local Hamiltonians via few quantum states

Becker, Lars, Joseph Slote, Alexander L'vovich Vol'berg +1 more

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.

arXiv:2509.11979•Sep 15, 2025•2 citations

A conjecture on a tight norm inequality in the finite-dimensional l_p

A. S. Holevo, A. V. Utkin

We suggest a tight inequality for norms in $d$-dimensional space $l_p $ which has simple formulation but appears hard to prove. We give a proof for $d=3$ and provide a detailed numerical check for $d\leq 200$ confirming the conjecture. We conclude with a brief survey of solutions for kin problems which anyhow concern minimization of the output entropy of certain quantum channel and rely upon the symmetry properties of the problem. Key words and phrases: $l_p $-norm, Rényi entropy, tight inequality, maximization of a convex function.

quant-pharXiv:2603.24017•Mar 26, 2026

Noncommutative Bohnenblust--Hille Inequality for qudit systems

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

Previous noncommutative Bohnenblust--Hille (BH) inequalities addressed operator decompositions in the tensor-product space $M_2(\mathbb{C})^{\otimes n}$; \emph{i.e.,} for systems of qubits \cite{HCP22,VZ23}. Here we prove noncommutative BH inequalities for operators decomposed in tensor-product spaces of arbitrary local dimension, \emph{i.e.,} $M_K(\mathbb{C})^{\otimes n}$ for any $K\geq2$ or on systems of $K$-level qudits. We treat operator decompositions in both the Gell-Mann and Heisenberg--Weyl basis, reducing to the recently-proved commutative hypercube BH \cite{DMP} and cyclic group BH \cite{SVZ} inequalities respectively. As an application we discuss learning qudit quantum observables.

arXiv:2406.08509•Jun 3, 2024•6 citations

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms

Francisco Escudero Gutiérrez, Miquel Saucedo, Carlos Palazuelos

We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials $p$ of degree $t$ satisfy a root-influence bound, $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t$. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as $t$-fold forrelation- are block-multilinear polynomials with $\|p\|_{\text{cb}}\leq 1,$ our inequality shows that they satisfy $t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}$. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial $p$ defined on $\{-1,1\}^n$ of degree $2t$, the Fourier Growth at the level $2t,$ namely $\|\widehat p_{2t}\|_{\ell_1}$, satisfies $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}$. This is optimal up to the factor $e$, as witnessed by $2t$-fold forrelation. As quantum query algorithms that make $t$ queries (to the whole input) satisfy $\|p\|_{\text{cb}}\leq 1$, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).

quant-pharXiv:2609.05201•Sep 7, 2026•2 citations

Dense Hamiltonians at the Parseval Limit: The Noncommutative BH Constant is Exponential and the Quantum FEI Conjecture is False

Joseph Slote

For each $d\geq 1$ we construct a norm-1 Hermitian operator whose Pauli expansion contains $N(d)=\exp(Ω(d^2))$ terms, each of degree $d$ and magnitude $1/\sqrt{N(d)}$ - the largest magnitude permitted by Parseval's identity. For comparison, if a bounded diagonal operator (or equivalently, a bounded degree-$d$ function on the Boolean cube) has $N(d)$ Pauli coefficients, all of magnitude $Ω(1/\sqrt{N(d)})$, then $N(d)\leq \exp(\widetilde{O}(d^{1.5}))$. This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies $\mathrm{BH}_{M_2}(d)\geq\exp(Ω(d))$. Together with the upper bounds proved in prior work, this settles the asymptotic growth of $\mathrm{BH}_{M_2}(d)$ as exponential. Our lower bound also asymptotically separates $\mathrm{BH}_{M_2}(d)$ from the (classical) hypercube BH constant $\mathrm{BH}_{\{\pm 1\}}(d)$, which in turn is known to be subexponential: $\mathrm{BH}_{\{\pm 1\}}(d)\leq C^{\sqrt{d \log d}}$. Our Hamiltonians are also unitary and thus quantum Boolean functions in the sense of Montanaro and Osborne (2010). As such they refute the quantum Fourier Entropy-Influence conjecture of Bu et al. (2024), a natural generalization of the classical Fourier Entropy-Influence conjecture due to Friedgut and Kalai (1996).

math.FACross-listedarXiv:2608.01424•Aug 4, 2026•4 citations

A sharp continuity estimate for the von Neumann entropy

Koenraad M. R. Audenaert

We derive an inequality relating the entropy difference between two quantum states to their trace norm distance, sharpening a well-known inequality due to Fannes. In our inequality, equality can be attained for every prescribed value of the trace norm distance.

arXiv:quant-ph/0610146•Journal of Physics A Mathematical and Theoretical•Jun 27, 2007•329 citations
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.
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∥≤C(d)max⁡ψ∈Xn∣⟨ψ∣A∣ψ⟩∣. \|A\|\le C(d)\max_{ψ\in \mathbf{X}_n}|\braket{ψ|A|ψ}|. ∥A∥≤C(d)maxψ∈Xn​​∣⟨ψ∣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$, 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 suggest a tight inequality for norms in ddd-dimensional space $l_p $ which has simple formulation but appears hard to prove. We give a proof for d=3d=3d=3 and provide a detailed numerical check for d≤200d\leq 200d≤200 confirming the conjecture. We conclude with a brief survey of solutions for kin problems which anyhow concern minimization of the output entropy of certain quantum channel and rely upon the symmetry properties of the problem. Key words and phrases: $l_p $-norm, Rényi entropy, tight inequality, maximization of a convex function.
Previous noncommutative Bohnenblust--Hille (BH) inequalities addressed operator decompositions in the tensor-product space M2(C)⊗nM_2(\mathbb{C})^{\otimes n}M2​(C)⊗n; \emph{i.e.,} for systems of qubits \cite{HCP22,VZ23}. Here we prove noncommutative BH inequalities for operators decomposed in tensor-product spaces of arbitrary local dimension, \emph{i.e.,} MK(C)⊗nM_K(\mathbb{C})^{\otimes n}MK​(C)⊗n for any K≥2K\geq2K≥2 or on systems of KKK-level qudits. We treat operator decompositions in both the Gell-Mann and Heisenberg--Weyl basis, reducing to the recently-proved commutative hypercube BH \cite{DMP} and cyclic group BH \cite{SVZ} inequalities respectively. As an application we discuss learning qudit quantum observables.
We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials ppp of degree ttt satisfy a root-influence bound, ∥p∥cb≥∑iInfi[p]/t2\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2∥p∥cb​≥∑i​Infi​[p]​/t2, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: ∥p∥cb≥∑iInfi[p]/t\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t∥p∥cb​≥∑i​Infi​[p]​/t. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as ttt-fold forrelation- are block-multilinear polynomials with ∥p∥cb≤1,\|p\|_{\text{cb}}\leq 1,∥p∥cb​≤1, our inequality shows that they satisfy t≥∑iInfi[p]t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}t≥∑i​Infi​[p]​. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial ppp defined on {−1,1}n\{-1,1\}^n{−1,1}n of degree 2t2t2t, the Fourier Growth at the level 2t,2t,2t, namely ∥p^2t∥ℓ1\|\widehat p_{2t}\|_{\ell_1}∥p​2t​∥ℓ1​​, satisfies ∥p^2t∥ℓ1≤(en/(2t−1))2t−12∥p∥cb\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}∥p​2t​∥ℓ1​​≤(en/(2t−1))22t−1​∥p∥cb​. This is optimal up to the factor eee, as witnessed by 2t2t2t-fold forrelation. As quantum query algorithms that make ttt queries (to the whole input) satisfy ∥p∥cb≤1\|p\|_{\text{cb}}\leq 1∥p∥cb​≤1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
For each d≥1d\geq 1d≥1 we construct a norm-1 Hermitian operator whose Pauli expansion contains N(d)=exp⁡(Ω(d2))N(d)=\exp(Ω(d^2))N(d)=exp(Ω(d2)) terms, each of degree ddd and magnitude 1/N(d)1/\sqrt{N(d)}1/N(d)​ - the largest magnitude permitted by Parseval's identity. For comparison, if a bounded diagonal operator (or equivalently, a bounded degree-ddd function on the Boolean cube) has N(d)N(d)N(d) Pauli coefficients, all of magnitude Ω(1/N(d))Ω(1/\sqrt{N(d)})Ω(1/N(d)​), then N(d)≤exp⁡(O~(d1.5))N(d)\leq \exp(\widetilde{O}(d^{1.5}))N(d)≤exp(O(d1.5)). This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies BHM2(d)≥exp⁡(Ω(d))\mathrm{BH}_{M_2}(d)\geq\exp(Ω(d))BHM2​​(d)≥exp(Ω(d)). Together with the upper bounds proved in prior work, this settles the asymptotic growth of BHM2(d)\mathrm{BH}_{M_2}(d)BHM2​​(d) as exponential. Our lower bound also asymptotically separates BHM2(d)\mathrm{BH}_{M_2}(d)BHM2​​(d) from the (classical) hypercube BH constant BH{±1}(d)\mathrm{BH}_{\{\pm 1\}}(d)BH{±1}​(d), which in turn is known to be subexponential: BH{±1}(d)≤Cdlog⁡d\mathrm{BH}_{\{\pm 1\}}(d)\leq C^{\sqrt{d \log d}}BH{±1}​(d)≤Cdlogd​. Our Hamiltonians are also unitary and thus quantum Boolean functions in the sense of Montanaro and Osborne (2010). As such they refute the quantum Fourier Entropy-Influence conjecture of Bu et al. (2024), a natural generalization of the classical Fourier Entropy-Influence conjecture due to Friedgut and Kalai (1996).