Quantum-inspired attribute selection algorithm: A Fidelity-based Quantum Decision Tree

• URL: http://arxiv.org/abs/2310.18243v1
• Date: Fri, 27 Oct 2023 16:29:42 GMT
• Title: Quantum-inspired attribute selection algorithm: A Fidelity-based Quantum Decision Tree
• Authors: Diksha Sharma, Parvinder Singh, Atul Kumar
• Abstract summary: A classical decision tree is completely based on splitting measures, which utilize the occurrence of random events in correspondence to its class labels. We propose to use fidelity as a quantum splitting criterion to construct an efficient and balanced quantum decision tree.
• Score: 1.6190746208019742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A classical decision tree is completely based on splitting measures, which utilize the occurrence of random events in correspondence to its class labels in order to optimally segregate datasets. However, the splitting measures are based on greedy strategy, which leads to construction of an imbalanced tree and hence decreases the prediction accuracy of the classical decision tree algorithm. An intriguing approach is to utilize the foundational aspects of quantum computing for enhancing decision tree algorithm. Therefore, in this work, we propose to use fidelity as a quantum splitting criterion to construct an efficient and balanced quantum decision tree. For this, we construct a quantum state using the occurrence of random events in a feature and its corresponding class. The quantum state is further utilized to compute fidelity for determining the splitting attribute among all features. Using numerical analysis, our results clearly demonstrate that the proposed algorithm cooperatively ensures the construction of a balanced tree. We further compared the efficiency of our proposed quantum splitting criterion to different classical splitting criteria on balanced and imbalanced datasets. Our simulation results show that the proposed splitting criterion exceeds all classical splitting criteria for all possible evaluation metrics.

Related papers

• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [3.9857517408503567]
  Quantum Approximate optimisation algorithm (qaoa) is a widely studied quantum-classical iterative for optimisation. We introduce a new algorithmic variant based on non-iterative computation that is instance-independent, but problem-specific. Our approach is based on proving a long-standing conjecture regarding quantum-independent structures in qaoa.
  arXiv  Detail & Related papers  (2024-08-12T21:02:58Z)
• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation [65.93830818469833]
  tensor networks and decision diagrams have independently been developed with differing perspectives, terminologies, and backgrounds in mind. We consider how these techniques approach classical quantum circuit simulation, and examine their (dis)similarities with regard to their most applicable abstraction level. We provide guidelines for when to better use tensor networks and when to better use decision diagrams in classical quantum circuit simulation.
  arXiv  Detail & Related papers  (2023-02-13T19:00:00Z)
• The Improvement of Decision Tree Construction Algorithm Based On Quantum Heuristic Algorithms [0.0]
  This work is related to the implementation of a decision tree construction algorithm on a quantum simulator. We consider an algorithm based on a binary criterion. Also, we study the improvement capability with quantum QAOA.
  arXiv  Detail & Related papers  (2022-12-28T15:41:40Z)
• 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)
• Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
  We introduce a quantum-control-inspired method for the characterization of variational quantum circuits using the rank of the dynamical Lie algebra. A promising connection is found between the Lie rank, the accuracy of calculated energies, and the requisite depth to attain target states via a given circuit architecture.
  arXiv  Detail & Related papers  (2022-09-28T20:24:53Z)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. The enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
  arXiv  Detail & Related papers  (2022-08-23T13:15:19Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Simulating quantum circuits using tree tensor networks [0.0]
  We develop and analyze a method for simulating quantum circuits on classical computers. Our algorithm first determines a suitable, fixed tree structure adapted to the expected entanglement generated by the quantum circuit. We theoretically analyze the applicability of the method as well as its computational cost and memory requirements.
  arXiv  Detail & Related papers  (2022-06-02T11:57:01Z)
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.0]
  Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up.
  arXiv  Detail & Related papers  (2022-03-06T14:04:06Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)

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.