Quantum boolean functions

Abstract

In this paper we introduce the study of quantum boolean functions, which are unitary operators f whose square is the identity: f^2 = I. We describe several generalisations of well-known results in the theory of boolean functions, including quantum property testing; a quantum version of the Goldreich-Levin algorithm for finding the large Fourier coefficients of boolean functions; and two quantum versions of a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. In order to obtain one of these generalisations, we prove a quantum extension of the hypercontractive inequality of Bonami, Gross and Beckner.

47 pages; v5: fixes previously corrupt file

References in corpus (1)

• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

Cited by in corpus (21)

• Quantum logarithmic Sobolev inequalities and rapid mixing
• Resource theory of quantum scrambling
• Hypercontractivity of quasi-free quantum semigroups
• A Survey of Quantum Property Testing
• Quantum Entropy and Central Limit Theorem
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• Pauli error estimation via Population Recovery
• Lectures on Quantum Tensor Networks
• Optimal Frobenius light cone in spin chains with power-law interactions
• On the mass of static metrics with positive cosmological constant -- II
• Quantum reverse hypercontractivity: its tensorization and application to strong converses
• Quantum reverse hypercontractivity
• Simulating Quantum Circuits with Sparse Output Distributions
• Representation of Boolean functions in terms of quantum computation
• Quantum Hashing via Classical $\epsilon$-universal Hashing Constructions
• Improved Quantum Hypercontractivity Inequality for the Qubit Depolarizing Channel
• Eigenlogic: a Quantum View for Multiple-Valued and Fuzzy Systems
• Quantum and Randomised Algorithms for Non-linearity Estimation
• Quantum algorithms for the Goldreich-Levin learning problem
• Interpolation Methods for Binary and Multivalued Logical Quantum Gate Synthesis
• Quantum certification of state set and unitary channel