In this paper, we resolve the quantum KKL conjecture of Montanaro and Osborne \cite{MO2010} for quantum Boolean functions on the $n$-qubit hypercube. More precisely, for every self-adjoint unitary $T$, we bound the largest $L_2$-influence from below by a constant multiple of $\mathrm{Var}(T)\log(n)/n$. The proof heavily depends on upper and lower commutator estimates on the Hilbert space.
In this paper, we resolve the quantum KKL conjecture of Montanaro and Osborne \cite{MO2010} for quantum Boolean functions on the n-qubit hypercube. More precisely, for every self-adjoint unitary T, we bound the largest L2-influence from below by a constant multiple of Var(T)log(n)/n. The proof heavily depends on upper and lower commutator estimates on the Hilbert space.
For each d≥1 we construct a norm-1 Hermitian operator whose Pauli expansion contains N(d)=exp(Ω(d2)) terms, each of degree d and magnitude 1/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/N(d)), then N(d)≤exp(O(d1.5)).
This construction implies the noncommutative Bohnenblust--Hille (BH) constant satisfies BHM2(d)≥exp(Ω(d)). Together with the upper bounds proved in prior work, this settles the asymptotic growth of BHM2(d) as exponential. Our lower bound also asymptotically separates BHM2(d) from the (classical) hypercube BH constant BH{±1}(d), which in turn is known to be subexponential: 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).
Some Monogamy Inequalities Based on the α-logarithmic Concurrence Measure for N-qubit States
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UAB by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary UAB whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(1)), where n is the dimension of systems A and B. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in n.
In this paper we consider the family of diagonal ±1 valued unitaries Uε, indexed by an element of the Boolean hypercube ε∈{±1}n2, i.e. Uε∣i⟩A∣j⟩B=εij∣i⟩A∣j⟩B. We show that if Uε can be implemented in NLQC with constant accuracy for all ε, and the dependency on ε in the first round of the associated strategy is a polynomial of degree O(n41−δ), then the implementation of at least one Uε in NLQC requires resources scaling as exp(Ω((logn)2n2δ)). The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
We extend three related results from the analysis of influences of Boolean functions to the quantum setting, namely the KKL theorem, Friedgut's Junta theorem and Talagrand's variance inequality for geometric influences. Our results are derived by a joint use of recently studied hypercontractivity and gradient estimates. These generic tools also allow us to derive generalizations of these results in a general von Neumann algebraic setting beyond the case of the quantum hypercube, including examples in infinite dimensions relevant to quantum information theory such as continuous variables quantum systems. Finally, we comment on the implications of our results as regards to noncommutative extensions of isoperimetric type inequalities, quantum circuit complexity lower bounds and the learnability of quantum observables.
Bohnenblust-Hille inequalities for Boolean cubes have been proven with dimension-free constants that grow subexponentially in the degree (Defant et al. in Math Ann 374(1):653-680, 2019). Such inequalities have found great applications in learning low-degree Boolean functions (Eskenazis and Ivanisvili in Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, pp 203-207, 2022). Motivated by learning quantum observables, a qubit analogue of Bohnenblust-Hille inequality for Boolean cubes was recently conjectured in Rouzé et al. (Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, 2022. arXiv preprint arXiv:2209.07279). The conjecture was resolved in Huang et al. (Learning to predict arbitrary quantum processes, 2022. arXiv preprint arXiv:2210.14894). In this paper, we give a new proof of these Bohnenblust-Hille inequalities for qubit system with constants that are dimension-free and of exponential growth in the degree. As a consequence, we obtain a junta theorem for low-degree polynomials. Using similar ideas, we also study learning problems of low degree quantum observables and Bohr's radius phenomenon on quantum Boolean cubes.