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

International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)

Learning Spectral Properties of Boolean Functions: A Unifying Theme in Quantum Algorithms

Mohsen Heidari, Amr Sabry

Published Sep 16, 2024• 0 citations
Publisher

Abstract

Quantum computing algorithms are often presented with a notation and perspective inspired by physics. We instead relate a family of quantum algorithms to the classical problem of learning spectral properties of boolean functions.
DOI
10.1109/synasc65383.2024.00013

Related papers

Quantum Algorithms Are Determining the Property of a Certain Function

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +3 more

We discuss a character of quantum algorithms. In fact, all of them determine the property of a certain function. The function under study must have the property $f(x) = f(-x)$ when $f(x)\neq 0$.

•Mar 1, 2017•0 citations

Quantum computing, norms and polynomials

Francisco Escudero Gutiérrez

In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.

•Mar 26, 2026•0 citations

THEORETICAL FOUNDATIONS OF CLASSICAL AND QUANTUM QUERY MODELS: COMPLEXITY, LOWER BOUNDS, AND POLYNOMIAL-SPECTRAL INTERPLAY

Medak Srinivas

Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.

Iterative International Publishers eBooks•May 1, 2026•0 citations

A survey of quantum learning

Richard Bonner, Rūsiņš Freivalds

We survey papers on problems of learning by quantum computers.The quest of quantum learning, as that of quantum computation,is to produce tractable quantum algorithms in situations, where tractable ...

•Jan 1, 2003•11 citations

Quantum Algorithms

Ted G. Lewis

This essay was written for computer scientists seeking to understand quantum computing from an algorithmic point of view. It sacrifices rigorous physics so anyone with a computer science background can understand it. Note that it is about algorithms, not machines. This is intentional.

Ubiquity•Mar 1, 2024•0 citations

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai +2 more

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is $\varepsilon$-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function $f$, of $n$ variables, is identical with a given function $g$ or is $\varepsilon$-far from $g$, where $\varepsilon$ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity $O(\frac{1}{\sqrt{\varepsilon}})$. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is $\Theta(\frac{1}{\varepsilon})$. Secondly, we consider the D-J problem from the perspective of functional correlations and let $C(f,g)$ denote the correlation of $f$ and $g$. We propose an exact quantum algorithm for making distinction between $|C(f,g)|=\varepsilon$ and $|C(f,g)|=1$ using six queries, while the classical deterministic query complexity for this problem is $\Theta(2^{n})$ queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus $\varepsilon$-far balanced using $O(\frac{1}{\varepsilon})$ queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of $O(1/\varepsilon^{2})$. Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae

arXiv:2109.06763•Fundamenta Informaticae•Nov 18, 2021•6 citations
We discuss a character of quantum algorithms. In fact, all of them determine the property of a certain function. The function under study must have the property f(x)=f(−x)f(x) = f(-x)f(x)=f(−x) when f(x)≠0f(x)\neq 0f(x)=0.
In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.
Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.
The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε\varepsilonε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function fff, of nnn variables, is identical with a given function ggg or is ε\varepsilonε-far from ggg, where ε\varepsilonε is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity O(1ε)O(\frac{1}{\sqrt{\varepsilon}})O(ε​1​). Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is Θ(1ε)\Theta(\frac{1}{\varepsilon})Θ(ε1​). Secondly, we consider the D-J problem from the perspective of functional correlations and let C(f,g)C(f,g)C(f,g) denote the correlation of fff and ggg. We propose an exact quantum algorithm for making distinction between ∣C(f,g)∣=ε|C(f,g)|=\varepsilon∣C(f,g)∣=ε and ∣C(f,g)∣=1|C(f,g)|=1∣C(f,g)∣=1 using six queries, while the classical deterministic query complexity for this problem is Θ(2n)\Theta(2^{n})Θ(2n) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ε\varepsilonε-far balanced using O(1ε)O(\frac{1}{\varepsilon})O(ε1​) queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ε2)O(1/\varepsilon^{2})O(1/ε2). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case. Comment: 24 pages, comments are welcome. It is accepted for publishing in Fundamenta Informaticae