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

Exact Learning with Tunable Quantum Neural Networks and a Quantum Example Oracle

Viet Pham Ngoc, Herbert Wiklicky

Published Sep 1, 2023• 0 citations
arXivHTMLPDF

Abstract

In this paper, we study the tunable quantum neural network architecture in the quantum exact learning framework with access to a uniform quantum example oracle. We present an approach that uses amplitude amplification to correctly tune the network to the target concept. We applied our approach to the class of positive $k$-juntas and found that $O(n^22^k)$ quantum examples are sufficient with experimental results seemingly showing that a tighter upper bound is possible.

DOI
10.48550/arxiv.2309.00561

Related papers

Tunable Quantum Neural Networks in the QPAC-Learning Framework

Viet Pham Ngoc, David Tuckey, Herbert Wiklicky

In this paper, we investigate the performances of tunable quantum neural networks in the Quantum Probably Approximately Correct (QPAC) learning framework. Tunable neural networks are quantum circuits made of multi-controlled X gates. By tuning the set of controls these circuits are able to approximate any Boolean functions. This architecture is particularly suited to be used in the QPAC-learning framework as it can handle the superposition produced by the oracle. In order to tune the network so that it can approximate a target concept, we have devised and implemented an algorithm based on amplitude amplification. The numerical results show that this approach can efficiently learn concepts from a simple class.

arXiv:2205.01514•Electronic Proceedings in Theoretical Computer Science•Nov 14, 2023•0 citations

Two new results about quantum exact learning

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +2 more

We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k -Fourier-sparse n -bit Boolean function from O(k1.5(log⁡k)2) uniform quantum examples for that function. This improves over the bound of Θ~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our O~(k1.5) upper bound by proving an improvement of Chang's lemma for k -Fourier-sparse Boolean functions. Second, we show that if a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned using O(Q2log⁡Qlog⁡|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log⁡Q -factor.

arXiv:1810.00481•Quantum•Nov 24, 2021•9 citations

Tunable Quantum Neural Networks for Boolean Functions

Viet Pham Ngoc, Herbert Wiklicky

In this paper we propose a new approach to quantum neural networks. Our multi-layer architecture avoids the use of measurements that usually emulate the non-linear activation functions which are characteristic of the classical neural networks. Despite this, our proposed architecture is still able to learn any Boolean function. This ability arises from the correspondence that exists between a Boolean function and a particular quantum circuit made out of multi-controlled NOT gates. This correspondence is built via a polynomial representation of the function called the algebraic normal form. We use this construction to introduce the idea of a generic quantum circuit whose gates can be tuned to learn any Boolean functions. In order to perform the learning task, we have devised an algorithm that leverages the absence of measurements. When presented with a superposition of all the binary inputs of length $n$, the network can learn the target function in at most $n+1$ updates.

arXiv:2003.14122•Mar 31, 2020•4 citations

Single-shot quantum neural networks with amplitude estimation

Jaemin Seo

Quantum neural networks (QNNs) suffer from a fundamental sampling bottleneck since quantum measurements are probabilistic, requiring many circuit executions to estimate outputs with sufficient accuracy. Conventional Monte-Carlo (MC) inference exhibits an $\mathcal{O}(1/\sqrt{N})$ sampling error, rendering QNN inference and training costly on near-term quantum hardware, especially where each shot requires expensive qubit generation. This work introduces a "single-shot" QNN framework by integrating quantum amplitude estimation (AE) into the readout stage. By embedding a trained QNN as a state-preparation oracle within AE, outputs are estimated through coherent interference rather than repeated sampling. We demonstrate that AE-based QNN inference achieves an $\mathcal{O}(1/N)$ error even with a single shot. We further analyze noise robustness and training feasibility, showing that AE can be a powerful primitive for overcoming the sampling overhead of QNNs. This highlights that when the model itself is quantum, quantum algorithms can enhance the computation efficiency.

quant-pharXiv:2604.19320•Apr 22, 2026•0 citations

Exploiting the equivalence between quantum neural networks and perceptrons

Chris Mingard, Jessica Pointing, London, Charles +2 more

Quantum machine learning models based on parametrized quantum circuits, also called quantum neural networks (QNNs), are considered to be among the most promising candidates for applications on near-term quantum devices. Here we explore the expressivity and inductive bias of QNNs by exploiting an exact mapping from QNNs with inputs $x$ to classical perceptrons acting on $x \otimes x$ (generalised to complex inputs). The simplicity of the perceptron architecture allows us to provide clear examples of the shortcomings of current QNN models, and the many barriers they face to becoming useful general-purpose learning algorithms. For example, a QNN with amplitude encoding cannot express the Boolean parity function for $n\geq 3$, which is but one of an exponential number of data structures that such a QNN is unable to express. Mapping a QNN to a classical perceptron simplifies training, allowing us to systematically study the inductive biases of other, more expressive embeddings on Boolean data. Several popular embeddings primarily produce an inductive bias towards functions with low class balance, reducing their generalisation performance compared to deep neural network architectures which exhibit much richer inductive biases. We explore two alternate strategies that move beyond standard QNNs. In the first, we use a QNN to help generate a classical DNN-inspired kernel. In the second we draw an analogy to the hierarchical structure of deep neural networks and construct a layered non-linear QNN that is provably fully expressive on Boolean data, while also exhibiting a richer inductive bias than simple QNNs. Finally, we discuss characteristics of the QNN literature that may obscure how hard it is to achieve quantum advantage over deep learning algorithms on classical data.

arXiv:2407.04371•Jul 5, 2024•0 citations

Two New Results About Quantum Exact Learning

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee +6 more

We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform quantum examples for that function. This improves over the bound of Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang’s lemma for sparse Boolean functions. Second, we show that if a concept class {C} can be exactly learned using Q quantum membership queries, then it can also be learned using O ({Q^2}/{log Q} * log|C|) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.

•Jan 1, 2019•10 citations
In this paper, we study the tunable quantum neural network architecture in the quantum exact learning framework with access to a uniform quantum example oracle. We present an approach that uses amplitude amplification to correctly tune the network to the target concept. We applied our approach to the class of positive kkk-juntas and found that O(n22k)O(n^22^k)O(n22k) quantum examples are sufficient with experimental results seemingly showing that a tighter upper bound is possible.
In this paper, we investigate the performances of tunable quantum neural networks in the Quantum Probably Approximately Correct (QPAC) learning framework. Tunable neural networks are quantum circuits made of multi-controlled X gates. By tuning the set of controls these circuits are able to approximate any Boolean functions. This architecture is particularly suited to be used in the QPAC-learning framework as it can handle the superposition produced by the oracle. In order to tune the network so that it can approximate a target concept, we have devised and implemented an algorithm based on amplitude amplification. The numerical results show that this approach can efficiently learn concepts from a simple class.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k -Fourier-sparse n -bit Boolean function from O(k1.5(log⁡k)2) uniform quantum examples for that function. This improves over the bound of Θ~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our O~(k1.5) upper bound by proving an improvement of Chang's lemma for k -Fourier-sparse Boolean functions. Second, we show that if a concept class C can be exactly learned using Q quantum membership queries, then it can also be learned using O(Q2log⁡Qlog⁡|C|) classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP'04) by a log⁡Q -factor.
In this paper we propose a new approach to quantum neural networks. Our multi-layer architecture avoids the use of measurements that usually emulate the non-linear activation functions which are characteristic of the classical neural networks. Despite this, our proposed architecture is still able to learn any Boolean function. This ability arises from the correspondence that exists between a Boolean function and a particular quantum circuit made out of multi-controlled NOT gates. This correspondence is built via a polynomial representation of the function called the algebraic normal form. We use this construction to introduce the idea of a generic quantum circuit whose gates can be tuned to learn any Boolean functions. In order to perform the learning task, we have devised an algorithm that leverages the absence of measurements. When presented with a superposition of all the binary inputs of length nnn, the network can learn the target function in at most n+1n+1n+1 updates.
Quantum neural networks (QNNs) suffer from a fundamental sampling bottleneck since quantum measurements are probabilistic, requiring many circuit executions to estimate outputs with sufficient accuracy. Conventional Monte-Carlo (MC) inference exhibits an O(1/N)\mathcal{O}(1/\sqrt{N})O(1/N​) sampling error, rendering QNN inference and training costly on near-term quantum hardware, especially where each shot requires expensive qubit generation. This work introduces a "single-shot" QNN framework by integrating quantum amplitude estimation (AE) into the readout stage. By embedding a trained QNN as a state-preparation oracle within AE, outputs are estimated through coherent interference rather than repeated sampling. We demonstrate that AE-based QNN inference achieves an O(1/N)\mathcal{O}(1/N)O(1/N) error even with a single shot. We further analyze noise robustness and training feasibility, showing that AE can be a powerful primitive for overcoming the sampling overhead of QNNs. This highlights that when the model itself is quantum, quantum algorithms can enhance the computation efficiency.
Quantum machine learning models based on parametrized quantum circuits, also called quantum neural networks (QNNs), are considered to be among the most promising candidates for applications on near-term quantum devices. Here we explore the expressivity and inductive bias of QNNs by exploiting an exact mapping from QNNs with inputs xxx to classical perceptrons acting on x⊗xx \otimes xx⊗x (generalised to complex inputs). The simplicity of the perceptron architecture allows us to provide clear examples of the shortcomings of current QNN models, and the many barriers they face to becoming useful general-purpose learning algorithms. For example, a QNN with amplitude encoding cannot express the Boolean parity function for n≥3n\geq 3n≥3, which is but one of an exponential number of data structures that such a QNN is unable to express. Mapping a QNN to a classical perceptron simplifies training, allowing us to systematically study the inductive biases of other, more expressive embeddings on Boolean data. Several popular embeddings primarily produce an inductive bias towards functions with low class balance, reducing their generalisation performance compared to deep neural network architectures which exhibit much richer inductive biases. We explore two alternate strategies that move beyond standard QNNs. In the first, we use a QNN to help generate a classical DNN-inspired kernel. In the second we draw an analogy to the hierarchical structure of deep neural networks and construct a layered non-linear QNN that is provably fully expressive on Boolean data, while also exhibiting a richer inductive bias than simple QNNs. Finally, we discuss characteristics of the QNN literature that may obscure how hard it is to achieve quantum advantage over deep learning algorithms on classical data.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k^{1.5}(log k)^2) uniform quantum examples for that function. This improves over the bound of Theta~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Our main tool is an improvement of Chang’s lemma for sparse Boolean functions. Second, we show that if a concept class {C} can be exactly learned using Q quantum membership queries, then it can also be learned using O ({Q^2}/{log Q} * log|C|) classical membership queries. This improves the previous-best simulation result (Servedio-Gortler, SICOMP'04) by a log Q-factor.