Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2408.08940

Quantum Algorithm for Jaccard Similarity

Varun Puram, Ruthvik Rao Bobbili, Johnson P. Thomas

Published Aug 16, 2024• 0 citations
arXivHTMLPDF

Abstract

Jaccard Similarity is a very common proximity measurement used to compute the similarity between two asymmetric binary vectors. Jaccard Similarity is the ratio between the 1s (Intersection of two vectors) to 1s (Union of two vectors). This paper introduces a quantum algorithm for finding the Jaccard Similarity 1s, in the Intersection and Union of two binary vectors. There are two sub-algorithms one for each. Measuring the register for respective algorithm gives count of number of 1 s in binary format. Implementation on IBM composer is also included.

DOI
10.48550/arxiv.2408.08940

Related papers

A Quantum Binary Classifier based on Cosine Similarity

Davide Pastorello, Enrico Blanzieri

This proposal introduces the quantum implementation of a binary classifier based on cosine similarity between data vectors. The proposed quantum algorithm presents time complexity that is logarithmic in the product of the training set cardinality and the dimension of the vectors. It is based just on a suitable state preparation like the retrieval from a QRAM, a SWAP test circuit, and a measurement process on a single qubit. An implementation on an IBM quantum processor is presented.

arXiv:2104.02975•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•7 citations

Applying a quantum amplification over a system for image feature matching and image recommendation

Desislav Andreev, Milena Kirilova Lazarova

A novel approach for improving the performance of a image feature matching and recommendation system is proposed that is a major continuation of the previous work in [3]. An advanced clustering method is suggested in order to deal with the binary image feature descriptors: a quantum variant of the k-majority algorithm over ORB descriptors. Jaccard-Needham dissimilarity measure is used as a distance measure step of the algorithm. Finally, the Grover's algorithm is used, providing the opportunity for a specific feature search in the database. The paper also provides the main steps in constructing a similar fast search system. The transformation from a classical to a quantum representation algorithm is described. Such approach can be applied in other applications. Both the computational complexity and the verification correctness are also indicated in the paper.

Balkan Conference in Informatics•Sep 5, 2019•1 citation

An Efficient Quantum Euclidean Similarity Algorithm for Worldwide Localization

Ahmed Shokry, Moustafa A. Youssef

Fingerprinting techniques are widely used for localization because of their accuracy, especially in the presence of wireless channel noise. However, the fingerprinting techniques require significant storage and running time, which is a concern when implementing such systems on a global worldwide scale. In this paper, we propose an efficient quantum Euclidean similarity algorithm for wireless localization systems. The proposed quantum algorithm offers exponentially improved complexity compared to its classical counterpart and even the state-of-the-art quantum localization systems, in terms of both storage space and running time. The basic idea is to entangle the test received signal strength (RSS) vector with the fingerprint vectors at different locations and perform the similarity calculation in parallel to all fingerprint locations. We give the details of how to construct the quantum fingerprint, how to encode the RSS measurements in quantum particles, and finally; present the quantum algorithm for calculating the Euclidean similarity between the online RSS measurements and the fingerprint ones. Implementation and evaluation of our algorithm in a real testbed using a real IBM quantum machine as well as a simulation for a larger testbed confirm its ability to correctly obtain the estimated location with an exponential enhancement in both time and space compared to the traditional classical fingerprinting techniques and the state-of-the-art quantum localization techniques.

arXiv:2407.14680•Jul 19, 2024•1 citation

Demonstration of Optimal Fixed-Point Quantum Search Algorithm in IBM Quantum Computer

Bikramaditya Das, Kamal Gurnani, Bikash K. Behera +1 more

A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. Quantum search algorithm can be described as the rotation of state vectors in a Hilbert space. The state vectors uniformly rotate by iterative sequences until they hit the target position. To optimize the algorithm, it is necessary to have the precise knowledge about some parameters like the number of target positions and total number of states. Here, we demonstrate the implementation of optimal fixed-point quantum search algorithm in IBMQ simulator developed by IBM corporation. We perform the search algorithm for one-iteration for two, three, four and five qubit systems and confirm the accuracy of our results through histogram.

arXiv:1712.10231•Dec 29, 2017•1 citation

A Simple Quantum Computation to Calculate Intersection of Data Sets

Ben-Qiong Hu

The computation of intersection of two data sets is an essential calculation in mathematics field.The computational efficiency is very low when the data sets consist of high dimensional vectors.In this paper,a unitary operation named general Grover iteration(GGI) is proposed and used to design quantum algorithm to calculate the intersection,and the algorithm is simple and fast than electronic computation significantly.

Journal of Sichuan Normal University•Jan 1, 2013•0 citations

A text classification algorithm based on quantum information

Songtao Shang, Minyong Shi, Wenqian Shang +1 more

Text classification is one of key problems in pattern recognition. The KNN algorithm is a widely used text classification algorithm, because it is simple, valid and non-parameters. The main idea of KNN algorithm is to calculate the similarity between the new sample with unknown class label and the training samples, and choosing the class label of the highest k nearest neighbors as the new sample's class label. However, the text contains hundreds and thousands of features. The similarity computing in large numbers of vector will cost many time. In fact that, many machine learning algorithms are unable to manipulate and compute large number of vectors in high-dimensional space. Quantum computing algorithms are good at computing high-dimensional vectors in large tensor product spaces. It can provide exponential speed-up over its classical counterparts. The N-dimensional quantum vectors represent 2N quantum superposition states. The similarity computing on the N-dimensional vectors is also on the 2N quantum superposition states simultaneously. Therefore, this paper introduces a KNN algorithms based on quantum computing, which uses fidelity to compute the similarity between two quantum states. The Control-Swap Test gate is very convenient as a fidelity estimator.

International Conference on Natural Computation (ICNC)•Aug 1, 2015•2 citations
Jaccard Similarity is a very common proximity measurement used to compute the similarity between two asymmetric binary vectors. Jaccard Similarity is the ratio between the 1s (Intersection of two vectors) to 1s (Union of two vectors). This paper introduces a quantum algorithm for finding the Jaccard Similarity 1s, in the Intersection and Union of two binary vectors. There are two sub-algorithms one for each. Measuring the register for respective algorithm gives count of number of 1 s in binary format. Implementation on IBM composer is also included.
A novel approach for improving the performance of a image feature matching and recommendation system is proposed that is a major continuation of the previous work in [3]. An advanced clustering method is suggested in order to deal with the binary image feature descriptors: a quantum variant of the k-majority algorithm over ORB descriptors. Jaccard-Needham dissimilarity measure is used as a distance measure step of the algorithm. Finally, the Grover's algorithm is used, providing the opportunity for a specific feature search in the database. The paper also provides the main steps in constructing a similar fast search system. The transformation from a classical to a quantum representation algorithm is described. Such approach can be applied in other applications. Both the computational complexity and the verification correctness are also indicated in the paper.
Fingerprinting techniques are widely used for localization because of their accuracy, especially in the presence of wireless channel noise. However, the fingerprinting techniques require significant storage and running time, which is a concern when implementing such systems on a global worldwide scale. In this paper, we propose an efficient quantum Euclidean similarity algorithm for wireless localization systems. The proposed quantum algorithm offers exponentially improved complexity compared to its classical counterpart and even the state-of-the-art quantum localization systems, in terms of both storage space and running time. The basic idea is to entangle the test received signal strength (RSS) vector with the fingerprint vectors at different locations and perform the similarity calculation in parallel to all fingerprint locations. We give the details of how to construct the quantum fingerprint, how to encode the RSS measurements in quantum particles, and finally; present the quantum algorithm for calculating the Euclidean similarity between the online RSS measurements and the fingerprint ones. Implementation and evaluation of our algorithm in a real testbed using a real IBM quantum machine as well as a simulation for a larger testbed confirm its ability to correctly obtain the estimated location with an exponential enhancement in both time and space compared to the traditional classical fingerprinting techniques and the state-of-the-art quantum localization techniques.
A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. Quantum search algorithm can be described as the rotation of state vectors in a Hilbert space. The state vectors uniformly rotate by iterative sequences until they hit the target position. To optimize the algorithm, it is necessary to have the precise knowledge about some parameters like the number of target positions and total number of states. Here, we demonstrate the implementation of optimal fixed-point quantum search algorithm in IBMQ simulator developed by IBM corporation. We perform the search algorithm for one-iteration for two, three, four and five qubit systems and confirm the accuracy of our results through histogram.
Text classification is one of key problems in pattern recognition. The KNN algorithm is a widely used text classification algorithm, because it is simple, valid and non-parameters. The main idea of KNN algorithm is to calculate the similarity between the new sample with unknown class label and the training samples, and choosing the class label of the highest k nearest neighbors as the new sample's class label. However, the text contains hundreds and thousands of features. The similarity computing in large numbers of vector will cost many time. In fact that, many machine learning algorithms are unable to manipulate and compute large number of vectors in high-dimensional space. Quantum computing algorithms are good at computing high-dimensional vectors in large tensor product spaces. It can provide exponential speed-up over its classical counterparts. The N-dimensional quantum vectors represent 2N quantum superposition states. The similarity computing on the N-dimensional vectors is also on the 2N quantum superposition states simultaneously. Therefore, this paper introduces a KNN algorithms based on quantum computing, which uses fidelity to compute the similarity between two quantum states. The Control-Swap Test gate is very convenient as a fidelity estimator.