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

Quantum Boosting

Srinivasan Arunachalam, Reevu Maity

Published Feb 12, 2020• 11 citations
arXivHTMLPDF

Abstract

Suppose we have a weak learning algorithm $\mathcal{A}$ for a Boolean-valued problem: $\mathcal{A}$ produces hypotheses whose bias $γ$ is small, only slightly better than random guessing (this could, for instance, be due to implementing $\mathcal{A}$ on a noisy device), can we boost the performance of $\mathcal{A}$ so that $\mathcal{A}$'s output is correct on $2/3$ of the inputs? Boosting is a technique that converts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by Freund and Schapire (for which they were awarded the Gödel prize in 2003) is one of the widely used boosting algorithms, with many applications in theory and practice. Suppose we have a $γ$-weak learner for a Boolean concept class $C$ that takes time $R(C)$, then the time complexity of AdaBoost scales as $VC(C)\cdot poly(R(C), 1/γ)$, where $VC(C)$ is the $VC$-dimension of $C$. In this paper, we show how quantum techniques can improve the time complexity of classical AdaBoost. To this end, suppose we have a $γ$-weak quantum learner for a Boolean concept class $C$ that takes time $Q(C)$, we introduce a quantum boosting algorithm whose complexity scales as $\sqrt{VC(C)}\cdot poly(Q(C),1/γ);$ thereby achieving a quadratic quantum improvement over classical AdaBoost in terms of $VC(C)$.

DOI
10.48550/arxiv.2002.05056

Related papers

Improved Quantum Boosting

Izdebski, Adam, Ronald de Wolf

Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity gave the first quantum improvement for boosting, by combining Freund and Schapire's AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner's hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio's SmoothBoost algorithm.

arXiv:2009.08360•Leibniz international proceedings in informatics•Sep 17, 2020•5 citations

Quantum boosting using domain-partitioning hypotheses

Sagnik Chatterjee, Rohan Bhatia, Parmeet Singh Chani +1 more

Abstract Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework. The AdaBoost algorithm is a well-known classical boosting algorithm for weak learners with binary hypotheses. Recently, Arunachalam and Maity presented the first quantum boosting algorithm by quantizing AdaBoost. Their algorithm, which we refer to as QAdaBoost hereafter, is a quantum adaptation of AdaBoost and only works for the binary hypothesis case. QAdaBoost is quadratically faster than AdaBoost in terms of the VC dimension of the hypothesis class of the weak learner. However, QAdaBoost is polynomially worse in the bias of the weak learner. In this work, we address an open question by Izdebski et al. on the existence of boosting algorithms for quantum weak learners with non-binary hypotheses. We answer this question in the affirmative by developing the QRealBoost algorithm motivated by the classical RealBoost algorithm. The main technical challenge was to provide provable guarantees for convergence, generalization bounds, and quantum speedup, given that quantum subroutines are noisy and probabilistic. We prove that QRealBoost retains the quadratic speedup of QAdaBoost over AdaBoost and further achieves a polynomial speedup over QAdaBoost in terms of both the bias of the learner and the time taken by the learner to learn the target concept class. Finally, we perform empirical evaluations on QRealBoost and report encouraging observations on quantum simulators by benchmarking the convergence performance of QRealBoost against QAdaBoost, AdaBoost, and RealBoost on a subset of the MNIST dataset and Breast Cancer Wisconsin dataset.

arXiv:2110.12793•Quantum Machine Intelligence•Jul 27, 2023•2 citations

QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses

Amira Abbas, Yanlin Chen, Tuyen Nguyen +1 more

The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple weak learners-hypotheses that are only slightly better than random guessing-into a single strong learner that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting.

arXiv:2510.05089•Oct 6, 2025•0 citations

Supervised-learning guarantee for quantum AdaBoost

Yabo Wang, Xin Wang, Bo Qi +1 more

In the noisy intermediate-scale quantum (NISQ) era, the capabilities of variational quantum algorithms are greatly constrained due to a limited number of qubits and the shallow depth of quantum circuits. We may view these variational quantum algorithms as weak learners in supervised learning. Ensemble methods are general approaches to combining weak learners to construct a strong one in machine learning. In this paper, by focusing on classification, we theoretically establish and numerically verify a learning guarantee for quantum adaptive boosting (AdaBoost). The supervised-learning risk bound describes how the prediction error of quantum AdaBoost on binary classification decreases as the number of boosting rounds and sample size increase. We further empirically demonstrate the advantages of quantum AdaBoost by focusing on a 4-class classification. The quantum AdaBoost not only outperforms several other ensemble methods, but in the presence of noise it can also surpass the ideally noiseless but unboosted primitive classifier after only a few boosting rounds. Our work indicates that in the current NISQ era, introducing appropriate ensemble methods is particularly valuable in improving the performance of quantum machine learning algorithms.

arXiv:2402.02376•Physical Review Applied•Nov 1, 2024•5 citations

Learning depth-3 circuits via quantum agnostic boosting

Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu +1 more

We initiate the study of quantum agnostic learning of phase states with respect to a function class $\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}$: given copies of an unknown $n$-qubit state $|ψ\rangle$ which has fidelity $\textsf{opt}$ with a phase state $|ϕ_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle$ for some $c\in \mathsf{C}$, output $|ϕ\rangle$ which has fidelity $|\langle ϕ| ψ\rangle|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: (i) Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. (ii) $s$-term DNF formulas in time $\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state $|ϕ\rangle$ such that $|\langle ϕ|ψ\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)$, into a strong learner which outputs a superposition of parity states $|ϕ'\rangle$ such that $|\langle ϕ'|ψ\rangle|^2\geq \textsf{opt} - \varepsilon$. Using quantum agnostic boosting, we obtain a $n^{O(\log(n/\varepsilon) \cdot \log \log n)}$-time algorithm for $\varepsilon$-learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform $\textsf{PAC}$ model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\textsf{PAC}$ model and our work answers this given quantum examples.

arXiv:2509.14461•Sep 17, 2025•0 citations

Quantum AdaBoost algorithm via cluster state

Yuanli Cai

The principle and theory of quantum computation are investigated by researchers for many years, and further applied to improve the efficiency of classical machine learning algorithms. Based on physical mechanism, a quantum version of AdaBoost (Adaptive Boosting) training algorithm is proposed in this paper, of which purpose is to construct a strong classifier. In the proposed scheme with cluster state in quantum mechanism is to realize the weak learning algorithm, and then update the corresponding weight of examples. As a result, a final classifier can be obtained by combining efficiently weak hypothesis based on measuring cluster state to reweight the distribution of examples.

International Journal of Modern Physics B•Dec 1, 2016•1 citation
Suppose we have a weak learning algorithm A\mathcal{A}A for a Boolean-valued problem: A\mathcal{A}A produces hypotheses whose bias γγγ is small, only slightly better than random guessing (this could, for instance, be due to implementing A\mathcal{A}A on a noisy device), can we boost the performance of A\mathcal{A}A so that A\mathcal{A}A's output is correct on 2/32/32/3 of the inputs? Boosting is a technique that converts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by Freund and Schapire (for which they were awarded the Gödel prize in 2003) is one of the widely used boosting algorithms, with many applications in theory and practice. Suppose we have a γγγ-weak learner for a Boolean concept class CCC that takes time R(C)R(C)R(C), then the time complexity of AdaBoost scales as VC(C)⋅poly(R(C),1/γ)VC(C)\cdot poly(R(C), 1/γ)VC(C)⋅poly(R(C),1/γ), where VC(C)VC(C)VC(C) is the VCVCVC-dimension of CCC. In this paper, we show how quantum techniques can improve the time complexity of classical AdaBoost. To this end, suppose we have a γγγ-weak quantum learner for a Boolean concept class CCC that takes time Q(C)Q(C)Q(C), we introduce a quantum boosting algorithm whose complexity scales as VC(C)⋅poly(Q(C),1/γ);\sqrt{VC(C)}\cdot poly(Q(C),1/γ);VC(C)​⋅poly(Q(C),1/γ); thereby achieving a quadratic quantum improvement over classical AdaBoost in terms of VC(C)VC(C)VC(C).
Boosting is a general method to convert a weak learner (which generates hypotheses that are just slightly better than random) into a strong learner (which generates hypotheses that are much better than random). Recently, Arunachalam and Maity gave the first quantum improvement for boosting, by combining Freund and Schapire's AdaBoost algorithm with a quantum algorithm for approximate counting. Their booster is faster than classical boosting as a function of the VC-dimension of the weak learner's hypothesis class, but worse as a function of the quality of the weak learner. In this paper we give a substantially faster and simpler quantum boosting algorithm, based on Servedio's SmoothBoost algorithm.
Abstract Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework. The AdaBoost algorithm is a well-known classical boosting algorithm for weak learners with binary hypotheses. Recently, Arunachalam and Maity presented the first quantum boosting algorithm by quantizing AdaBoost. Their algorithm, which we refer to as QAdaBoost hereafter, is a quantum adaptation of AdaBoost and only works for the binary hypothesis case. QAdaBoost is quadratically faster than AdaBoost in terms of the VC dimension of the hypothesis class of the weak learner. However, QAdaBoost is polynomially worse in the bias of the weak learner. In this work, we address an open question by Izdebski et al. on the existence of boosting algorithms for quantum weak learners with non-binary hypotheses. We answer this question in the affirmative by developing the QRealBoost algorithm motivated by the classical RealBoost algorithm. The main technical challenge was to provide provable guarantees for convergence, generalization bounds, and quantum speedup, given that quantum subroutines are noisy and probabilistic. We prove that QRealBoost retains the quadratic speedup of QAdaBoost over AdaBoost and further achieves a polynomial speedup over QAdaBoost in terms of both the bias of the learner and the time taken by the learner to learn the target concept class. Finally, we perform empirical evaluations on QRealBoost and report encouraging observations on quantum simulators by benchmarking the convergence performance of QRealBoost against QAdaBoost, AdaBoost, and RealBoost on a subset of the MNIST dataset and Breast Cancer Wisconsin dataset.
The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple weak learners-hypotheses that are only slightly better than random guessing-into a single strong learner that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting.
In the noisy intermediate-scale quantum (NISQ) era, the capabilities of variational quantum algorithms are greatly constrained due to a limited number of qubits and the shallow depth of quantum circuits. We may view these variational quantum algorithms as weak learners in supervised learning. Ensemble methods are general approaches to combining weak learners to construct a strong one in machine learning. In this paper, by focusing on classification, we theoretically establish and numerically verify a learning guarantee for quantum adaptive boosting (AdaBoost). The supervised-learning risk bound describes how the prediction error of quantum AdaBoost on binary classification decreases as the number of boosting rounds and sample size increase. We further empirically demonstrate the advantages of quantum AdaBoost by focusing on a 4-class classification. The quantum AdaBoost not only outperforms several other ensemble methods, but in the presence of noise it can also surpass the ideally noiseless but unboosted primitive classifier after only a few boosting rounds. Our work indicates that in the current NISQ era, introducing appropriate ensemble methods is particularly valuable in improving the performance of quantum machine learning algorithms.
We initiate the study of quantum agnostic learning of phase states with respect to a function class C⊆{c:{0,1}n→{0,1}}\mathsf{C}\subseteq \{c:\{0,1\}^n\rightarrow \{0,1\}\}C⊆{c:{0,1}n→{0,1}}: given copies of an unknown nnn-qubit state ∣ψ⟩|ψ\rangle∣ψ⟩ which has fidelity opt\textsf{opt}opt with a phase state ∣ϕc⟩=12n∑x∈{0,1}n(−1)c(x)∣x⟩|ϕ_c\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{c(x)}|x\rangle∣ϕc​⟩=2n​1​∑x∈{0,1}n​(−1)c(x)∣x⟩ for some c∈Cc\in \mathsf{C}c∈C, output ∣ϕ⟩|ϕ\rangle∣ϕ⟩ which has fidelity ∣⟨ϕ∣ψ⟩∣2≥opt−ε|\langle ϕ| ψ\rangle|^2 \geq \textsf{opt}-\varepsilon∣⟨ϕ∣ψ⟩∣2≥opt−ε. To this end, we give agnostic learning protocols for the following classes: (i) Size-ttt decision trees which runs in time poly(n,t,1/ε)\textsf{poly}(n,t,1/\varepsilon)poly(n,t,1/ε). This also implies kkk-juntas can be agnostically learned in time poly(n,2k,1/ε)\textsf{poly}(n,2^k,1/\varepsilon)poly(n,2k,1/ε). (ii) sss-term DNF formulas in time poly(n,(s/ε)log⁡log⁡(s/ε)⋅log⁡(1/ε))\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})poly(n,(s/ε)loglog(s/ε)⋅log(1/ε)). Our main technical contribution is a quantum agnostic boosting protocol which converts a weak agnostic learner, which outputs a parity state ∣ϕ⟩|ϕ\rangle∣ϕ⟩ such that ∣⟨ϕ∣ψ⟩∣2≥opt/poly(n)|\langle ϕ|ψ\rangle|^2\geq \textsf{opt}/\textsf{poly}(n)∣⟨ϕ∣ψ⟩∣2≥opt/poly(n), into a strong learner which outputs a superposition of parity states ∣ϕ′⟩|ϕ'\rangle∣ϕ′⟩ such that ∣⟨ϕ′∣ψ⟩∣2≥opt−ε|\langle ϕ'|ψ\rangle|^2\geq \textsf{opt} - \varepsilon∣⟨ϕ′∣ψ⟩∣2≥opt−ε. Using quantum agnostic boosting, we obtain a nO(log⁡(n/ε)⋅log⁡log⁡n)n^{O(\log(n/\varepsilon) \cdot \log \log n)}nO(log(n/ε)⋅loglogn)-time algorithm for ε\varepsilonε-learning poly(n)\textsf{poly}(n)poly(n)-sized depth-333 circuits (consisting of AND\textsf{AND}AND, OR\textsf{OR}OR, NOT\textsf{NOT}NOT gates) in the uniform PAC\textsf{PAC}PAC model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the PAC\textsf{PAC}PAC model and our work answers this given quantum examples.
The principle and theory of quantum computation are investigated by researchers for many years, and further applied to improve the efficiency of classical machine learning algorithms. Based on physical mechanism, a quantum version of AdaBoost (Adaptive Boosting) training algorithm is proposed in this paper, of which purpose is to construct a strong classifier. In the proposed scheme with cluster state in quantum mechanism is to realize the weak learning algorithm, and then update the corresponding weight of examples. As a result, a final classifier can be obtained by combining efficiently weak hypothesis based on measuring cluster state to reweight the distribution of examples.