Quantum Classification Outside the Promised Class
Open Access
Abstract
This paper studies the important problem of quantum classification of Boolean functions from an entirely novel perspective. Typically, quantum classification algorithms allow us to classify functions with a probability of , 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 a large class of imbalanced Boolean functions with probability using just a single oracular query. First, we establish a completely new concept characterizing “nearness” between Boolean functions. Utilizing this concept, we show that, as long as the unknown 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.
Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Distributed Generalized Deutsch-Jozsa Algorithm2025
- Interferometric single-shot parity measurement in InAs–Al hybrid devicesNature, 2025
- Distributed quantum computing across an optical network linkNature, 2025
- A generalisation of the Phase Kick-BackQuantum Information Processing, 2023
- Revisiting Deutsch-Jozsa algorithmInformation and Computation, 2020
- Generalization of Deutsch’s AlgorithmInternational Journal of Theoretical Physics, 2020
- Non-local quantum functions and the distributed Deutsch-Jozsa algorithmPhysics Letters A, 2019
- A quantum speedup in machine learning: finding anN-bit Boolean function for a classificationNew Journal of Physics, 2014
- The geometry of quantum learningQuantum Information Processing, 2009
- Generating Equiprobable Superpositions of Arbitrary Sets for a New Generalization of the Deutsch-Jozsa AlgorithmLecture Notes in Computer Science, 2004