Quantum Classification Outside the Promised Class

• URL: http://arxiv.org/abs/2504.18898v1
• Date: Sat, 26 Apr 2025 11:50:58 GMT
• Title: Quantum Classification Outside the Promised Class
• Authors: Theodore Andronikos, Constantinos Bitsakos, Konstantinos Nikas, Georgios I. Goumas, Nectarios Koziris,
• Abstract summary: We investigate whether it is feasible to obtain insights when the input function deviates from the promised class.<n>We use a recently introduced quantum algorithm that is designed to classify with probability $1.0$ using just a single oracular query.<n>We show that, as long as the input function is close enough to the promised class, it is still possible to obtain useful information.
• Score: 2.209328709671456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the important problem of quantum classification of Boolean functions from a entirely novel perspective. Typically, quantum classification algorithms allow us to classify functions with a probability of $1.0$, if we are promised that they meet specific unique properties. The primary objective of this study is to explore whether it is feasible to obtain any insights when the input function deviates from the promised class. For concreteness, we use a recently introduced quantum algorithm that is designed to classify with probability $1.0$ using just a single oracular query a large class of imbalanced Boolean functions. Fist, we establish a completely new concept characterizing ``nearness'' between Boolean function. Utilizing this concept, we show that, as long as the input function is close enough to the promised class, it is still possible to obtain useful information about its behavioral pattern from the classification algorithm. In this regard, the current study is among the first to provide evidence that shows how useful it is to apply quantum classification algorithms to functions outside the promised class in order to get a glimpse of important information.

Related papers

• Quantum machine learning advantages beyond hardness of evaluation [1.9662978733004604]
  Most general examples of quantum learning advantages involve data labeled by cryptographic or quantum functions.<n>For quantum functions, random-generatability is conjectured not to hold, leaving no known identification advantages in genuinely quantum regimes.<n>We show that verifiable identification is hard for quantum labeling functions unless BQP is in the hierarchy.
  arXiv  Detail & Related papers  (2025-04-22T15:04:46Z)
• A Quantum Algorithm for the Classification of Patterns of Boolean Functions [2.209328709671456]
  This paper introduces a novel quantum algorithm that is able to classify a hierarchy of classes of imbalanced Boolean functions.<n>Our algorithm achieves classification in a straightforward manner as the final measurement reveals the unknown function with probability $1$.
  arXiv  Detail & Related papers  (2025-03-14T00:26:36Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• Quantum-inspired classification based on quantum state discrimination [0.774229787612056]
  We present quantum-inspired algorithms for classification tasks inspired by the problem of quantum state discrimination. By construction, these algorithms can perform multiclass classification, prevent overfitting, and generate probability outputs. While they could be implemented on a quantum computer, we focus here on classical implementations of such algorithms.
  arXiv  Detail & Related papers  (2023-03-27T16:09:40Z)
• Special functions in quantum phase estimation [61.12008553173672]
  We focus on two special functions. One is prolate spheroidal wave function, which approximately gives the maximum probability that the difference between the true parameter and the estimate is smaller than a certain threshold. The other is Mathieu function, which exactly gives the optimum estimation under the energy constraint.
  arXiv  Detail & Related papers  (2023-02-14T08:33:24Z)
• A didactic approach to quantum machine learning with a single qubit [68.8204255655161]
  We focus on the case of learning with a single qubit, using data re-uploading techniques. We implement the different proposed formulations in toy and real-world datasets using the qiskit quantum computing SDK.
  arXiv  Detail & Related papers  (2022-11-23T18:25:32Z)
• About the description of physical reality of Bell's experiment [91.3755431537592]
  A hidden variables model complying with the simplest form of Local Realism was recently introduced. It reproduces Quantum Mechanics' predictions for an even ideally perfect Bell's experiment. A new type of quantum computer does not exist yet, not even in theory.
  arXiv  Detail & Related papers  (2021-09-06T15:55:13Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Characterization of exact one-query quantum algorithms (ii): for partial functions [0.2741266294612775]
  The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity.
  arXiv  Detail & Related papers  (2020-08-27T09:06:34Z)
• Tunable Quantum Neural Networks for Boolean Functions [0.0]
  We 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.
  arXiv  Detail & Related papers  (2020-03-31T11:55:01Z)
• Quantum noise protects quantum classifiers against adversaries [120.08771960032033]
  Noise in quantum information processing is often viewed as a disruptive and difficult-to-avoid feature, especially in near-term quantum technologies. We show that by taking advantage of depolarisation noise in quantum circuits for classification, a robustness bound against adversaries can be derived. This is the first quantum protocol that can be used against the most general adversaries.
  arXiv  Detail & Related papers  (2020-03-20T17:56:14Z)
• Options of Interest: Temporal Abstraction with Interest Functions [58.30081828754683]
  We provide a generalization of initiation sets suitable for general function approximation, by defining an interest function associated with an option. We derive a gradient-based learning algorithm for interest functions, leading to a new interest-option-critic architecture.
  arXiv  Detail & Related papers  (2020-01-01T21:24:39Z)

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.