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
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
A provable exponential quantum speedup has been a central research goal since the seminal HHL quantum algorithm for solving linear systems.
We present the first such provable exponential separation between quantum and quantum-inspired classical algorithms.
arXiv Detail & Related papers (2024-11-04T13:49:26Z) - 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) - 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) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm.
We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with.
Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
arXiv Detail & Related papers (2020-12-03T07:12:08Z)
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.