Efficient Quantum Agnostic Improper Learning of Decision Trees
- URL: http://arxiv.org/abs/2210.00212v3
- Date: Wed, 6 Mar 2024 06:34:53 GMT
- Title: Efficient Quantum Agnostic Improper Learning of Decision Trees
- Authors: Sagnik Chatterjee, Tharrmashastha SAPV, Debajyoti Bera
- Abstract summary: We give a poly agnostic(n,t,frac1varepsilon)$ quantum algorithm for learning size $t$ decision trees with uniform marginal over instances.
Our algorithm is the first algorithm (classical or quantum) for learning decision trees in time without membership queries.
- Score: 0.18416014644193066
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The agnostic setting is the hardest generalization of the PAC model since it
is akin to learning with adversarial noise. In this paper, we give a
poly$(n,t,{\frac{1}{\varepsilon}})$ quantum algorithm for learning size $t$
decision trees with uniform marginal over instances, in the agnostic setting,
without membership queries. Our algorithm is the first algorithm (classical or
quantum) for learning decision trees in polynomial time without membership
queries. We show how to construct a quantum agnostic weak learner by designing
a quantum version of the classical Goldreich-Levin algorithm that works with
strongly biased function oracles. We show how to quantize the agnostic boosting
algorithm by Kalai and Kanade (NIPS 2009) to obtain the first efficient quantum
agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial
improvement in the dependence of the bias of the weak learner over all adaptive
quantum boosting algorithms while retaining the standard speedup in the VC
dimension over classical boosting algorithms. We then use our quantum boosting
algorithm to boost the weak quantum learner we obtained in the previous step to
obtain a quantum agnostic learner for decision trees. Using the above
framework, we also give quantum decision tree learning algorithms for both the
realizable setting and random classification noise model, again without
membership queries.
Related papers
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms.
We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
arXiv Detail & Related papers (2023-09-22T18:00:03Z) - Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
We introduce an iterative quantum optimization algorithm to solve optimization problems.
We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits.
We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement.
arXiv Detail & Related papers (2023-03-09T18:59:37Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum Bayes AI [1.7403133838762443]
Quantum Bayesian AI (Q-B) is an emerging field that levers the computational gains available in Quantum computing.
We provide a duality between classical and quantum probability for calculating of posterior quantities of interest.
We illustrate the behaviour of quantum algorithms on two simple classification algorithms.
arXiv Detail & Related papers (2022-08-17T04:51:10Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum Inspired Adaptive Boosting [0.0]
We show that the quantum ensemble method does not have advantage over classical algorithms.
We propose methods inspired by combining the quantum ensemble method with adaptive boosting.
The algorithms were tested and found to be comparable to the AdaBoost algorithm on publicly available data sets.
arXiv Detail & Related papers (2021-02-01T16:33:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.