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.
We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size s is concentrated on coefficients of degree up to O( √ s). These results have several applications that apply to any function f that can be computed by a deMorgan formula of size s. First, we get that f can be approximated (in L2-norm) with constant error by a polynomial of degree O( √ s). Second, we show an upper bound of O( √ s) on the average sensitivity of f . Our main result stems from a generalization of Khrapchenko’s bound [Khr71], that might be of independent interest, and some Fourier analysis on the Boolean cube. Previous works prove that any function f : {0, 1}n → {0, 1} that can be computed by a deMorgan formula of size s, can be approximated point-wise by a polynomial of degree O(s/2+o(1)) with constant point-wise error. We note that this result can be easily extended to have a polynomial of degree O(t ·s/2+o(1)) that approximates f with point-wise error 2−t, for any t > 0. This was shown in a long line of results in quantum complexity, including [BBC+01] and [FGG08, ACR+07, RS08, Rei09].
Categorical data plays an important part in machine learning research and appears in a variety of applications. Models that can express large classes of real-valued functions on the Boolean cube are useful for problems involving discrete-valued data types, including those which are not Boolean. To this date, the commonly used schemes for embedding classical data into variational quantum machine learning models encode continuous values. Here we investigate quantum embeddings for encoding Boolean-valued data into parameterized quantum circuits used for machine learning tasks. We narrow down representability conditions for functions on then-dimensional Boolean cube with respect to previously known results, using two quantum embeddings: a phase embedding and an embedding based on quantum random access codes. We show that for any real-valued function on then-dimensional Boolean cube, there exists a variational linear quantum model based on a phase embedding usingnqubits that can represent it and an ensemble of such models using
d<nqubits that can express any function with degree at most d. Additionally, we prove that variational linear quantum models that use the quantum random access code embedding can express functions on the Boolean cube with degree
d≤⌈3n⌉using
⌈3n⌉qubits, and that an ensemble of such models can represent any function on the Boolean cube with degree
d≤⌈3n⌉. Furthermore, we discuss the potential benefits of each embedding and the impact of serial repetitions. Lastly, we demonstrate the use of the embeddings presented by performing numerical simulations and experiments on IBM quantum processors using the Qiskit machine learning framework.