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:2108.02014

A unified picture of Balance puzzles and Group testing: Some lessons from quantum mechanics for the pandemic

Chetan Waghela

Published Aug 4, 2021• 1 citation
arXivHTMLPDF

Abstract

Balance (Counterfeit coin) puzzles have been part of recreational mathematics for a few decades. A particular type of Counterfeit coin puzzle is known in the literature as the "Beam balance puzzle". An abstract solution to it is provided by Iwama et.al as a modification of the Bernstein-Vazirani algorithm, making use of quantum parallelism and entanglement. Moreover, during this pandemic, group testing has proved to be an efficient algorithm to save time and cost of testing specimens for the presence of infection. In this article, we propose a "Binary Spring Balance" (BSB) puzzle, to facilitate a unified picture of the counterfeit coin problem and the testing for infection problem, as both aim to reduce the number of queries. We then showcase two solutions to the BSB problem, one using bits and other using classical-qubits ('cebits") for querying. Both solutions are demonstrated using circuits. In this pursuit, we develop a modified optical implementation of Bernstein-Vazirani algorithm using only polarizers (no need of beam splitters), which has surprisingly not yet been proposed earlier. Under the pretext of this demonstration we question why we have not yet developed testing mechanisms inspired by Bernstein-Vazirani algorithm for the pandemic, as they solve the problem in single query, they have no issues related to prevalence of infection in the population, nor are they plagued by the issue of dilution of samples due to pooling. The modified implementation of Bernstein-Vazirani algorithm using polarizers can also be a cost-effective demonstration in an undergraduate lab.

DOI
10.48550/arxiv.2108.02014

Related papers

Implementation of the Bernstein-Vazirani Quantum Algorithm Using the Qiskit Framework

Alexandru-Gabriel Tudorache, Vasile Manta, Simona Caraiman

Abstract This paper describes the basics of quantum computing and then focuses on the implementation of the Bernstein-Vazirani algorithm, which can be seen as an extension of the Deutsch-Josza problem (that solves the question on whether a function is balanced or not). The idea behind the B-V algorithm is that someone can find a secret number (sequence of bits) using only one measurement, unlike the classical counter-part, that requires n measurements, where n is the number of bits of the secret number. The implementation of this algorithm, using the Python programming language, along with the Qiskit framework (an open-source library for quantum operations from IBM), illustrates how to create and simulate a circuit for such an algorithm. The circuit is dynamically generated for the required number (which in practice is received from a different source) and is used to measure the probability of each qubit. The algorithm can also be extended for different types of data and can be used for signal or image processing, as well as applications in cryptography.

Buletinul Institutului Politehnic din Iaşi. Secţia Electrotehnică. Energetică. Electronică•Jun 1, 2021•3 citations

Implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement on an ensemble quantum computer

Jiangfeng Du, Mingjun Shi, Xianyi Zhou +4 more

Bernstein and Varizani have given the first quantum algorithm to solve the parity problem in which a strong violation of the classical information theoretic bound comes about. In this paper we refine this algorithm with fewer resources and implement a two-qubit algorithm in a single query on an ensemble quantum computer.

arXiv:quant-ph/0012114•Physical Review A•Sep 11, 2001•51 citations

Entanglement and coherence in the Bernstein-Vazirani algorithm

Moein Naseri, Tulja Varun Kondra, Suchetana Goswami +2 more

Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. 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. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.

arXiv:2205.13610•Physical Review A•Dec 21, 2022•38 citations

Developing A Quantum Circuit Simulator API

Stancu Mihai Dorian, Popa Emil Marin

Abstract In this paper we propose the design and implementation of a quantum circuit simulator API. Currently the API allows users to implement, debug and test the following two quantum algorithms: Bernstein-Vazirani’s algorithm and Simon’s Algorithm. The goal is to create a framework that will allow quantum computer scientists to easily develop new quantum algorithms.

Acta Universitatis Cibiniensis Technical Series•Sep 1, 2015•0 citations

Implementation of the Bernstein–Vazirani Quantum Algorithm on the IBM Q Computers

Sydney Wang, Athena Zheng

The complexity of certain classical computer algorithms can be reduced by a quantum algorithm completing the same task. We examine the implementation of the Bernstein–Vazirani algorithm. It finds the hidden n-bit string s from the function fs(x)=sx that takes an n-bit input string x and outputs one bit, the dot product. This algorithm reduces the complexity from n queries for the best classical algorithm to just one. Though the quantum algorithm theoretically always gives the correct string, in practice, factors such as decoherence of the physical qubits due to external noise reduce the algorithm’s accuracy. By implementing the algorithm on the IBM 5-qubit and 14-qubit quantum computers, we are able to analyze correlations between the accuracy of the results and the properties of the physical qubits used. Not all qubits are pairwise connected, nor do they have the same coherence times. Using Python to build the quantum circuits, we create several implementations of the circuit with different qubits. We establish that 1/T1, 1/T2, and gate errors are positively correlated with calculation errors. Consequently, we observe that the 14-qubit quantum computer, on average, is more prone to errors than the 5-qubit quantum computer.

•Jan 1, 2019•0 citations

Distributed exact quantum algorithms for Bernstein-Vazirani and search problems

Zhou Xu, Daowen Qiu, Lou, Le

Distributed quantum computation has gained extensive attention since small-qubit quantum computers seem to be built more practically in the noisy intermediate-scale quantum (NISQ) era. In this paper, we give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. Though the designing techniques are simple in the light of BV algorithm, Grover's algorithm, the improved Grover's algorithm by Long, and the distributed Grover's algorithm by Qiu et al, in comparison to BV algorithm, the circuit depth of DBVA is not greater than $2^{\text{max}(n_0, n_1, \cdots, n_{t-1})}+3$ instead of $2^{n}+3$, and the circuit depth of DEGA is $8(n~\text{mod}~2)+9$, which is less than the circuit depth of Grover's algorithm, $1 + 8\left\lfloor \fracπ{4}\sqrt{2^n} \right\rfloor$. In particular, we provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods. By simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithm has superiority of resisting noise.

arXiv:2303.10670•Mar 19, 2023•9 citations
Balance (Counterfeit coin) puzzles have been part of recreational mathematics for a few decades. A particular type of Counterfeit coin puzzle is known in the literature as the "Beam balance puzzle". An abstract solution to it is provided by Iwama et.al as a modification of the Bernstein-Vazirani algorithm, making use of quantum parallelism and entanglement. Moreover, during this pandemic, group testing has proved to be an efficient algorithm to save time and cost of testing specimens for the presence of infection. In this article, we propose a "Binary Spring Balance" (BSB) puzzle, to facilitate a unified picture of the counterfeit coin problem and the testing for infection problem, as both aim to reduce the number of queries. We then showcase two solutions to the BSB problem, one using bits and other using classical-qubits ('cebits") for querying. Both solutions are demonstrated using circuits. In this pursuit, we develop a modified optical implementation of Bernstein-Vazirani algorithm using only polarizers (no need of beam splitters), which has surprisingly not yet been proposed earlier. Under the pretext of this demonstration we question why we have not yet developed testing mechanisms inspired by Bernstein-Vazirani algorithm for the pandemic, as they solve the problem in single query, they have no issues related to prevalence of infection in the population, nor are they plagued by the issue of dilution of samples due to pooling. The modified implementation of Bernstein-Vazirani algorithm using polarizers can also be a cost-effective demonstration in an undergraduate lab.
Abstract This paper describes the basics of quantum computing and then focuses on the implementation of the Bernstein-Vazirani algorithm, which can be seen as an extension of the Deutsch-Josza problem (that solves the question on whether a function is balanced or not). The idea behind the B-V algorithm is that someone can find a secret number (sequence of bits) using only one measurement, unlike the classical counter-part, that requires n measurements, where n is the number of bits of the secret number. The implementation of this algorithm, using the Python programming language, along with the Qiskit framework (an open-source library for quantum operations from IBM), illustrates how to create and simulate a circuit for such an algorithm. The circuit is dynamically generated for the required number (which in practice is received from a different source) and is used to measure the probability of each qubit. The algorithm can also be extended for different types of data and can be used for signal or image processing, as well as applications in cryptography.
Quantum algorithms can outperform their classical counterparts in various tasks, the most prominent example being Shor's algorithm for efficient prime factorization on a quantum computer. It is clear that one of the reasons for the speedup is the superposition principle of quantum mechanics, which allows a quantum processor to be in a superposition of different states at the same time. While such a superposition can lead to entanglement across different qubits of the processors, there also exist quantum algorithms that outperform classical ones using superpositions of individual qubits without entangling them. As an example, the Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. While the classical version of the algorithm requires multiple calls of the oracle to learn the bit string, a single query of the oracle is enough in the quantum case. In this article, we analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. For this, we introduce and study its probabilistic version, where the goal is to guess the bit string after a single call of the oracle. 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. We further demonstrate that a large amount of entanglement in the initial state prevents the algorithm from achieving optimal performance. We also apply our methods to quantum computation with mixed states, proving that pseudopure states achieve optimal performance for a given purity in the Bernstein-Vazirani algorithm. We further investigate quantum resources in the one clean qubit model, showing that the model can exhibit speedup over any known classical algorithm even with an arbitrarily little amount of multipartite entanglement, general quantum correlations, and coherence.
The complexity of certain classical computer algorithms can be reduced by a quantum algorithm completing the same task. We examine the implementation of the Bernstein–Vazirani algorithm. It finds the hidden n-bit string s from the function fs(x)=sx that takes an n-bit input string x and outputs one bit, the dot product. This algorithm reduces the complexity from n queries for the best classical algorithm to just one. Though the quantum algorithm theoretically always gives the correct string, in practice, factors such as decoherence of the physical qubits due to external noise reduce the algorithm’s accuracy. By implementing the algorithm on the IBM 5-qubit and 14-qubit quantum computers, we are able to analyze correlations between the accuracy of the results and the properties of the physical qubits used. Not all qubits are pairwise connected, nor do they have the same coherence times. Using Python to build the quantum circuits, we create several implementations of the circuit with different qubits. We establish that 1/T1, 1/T2, and gate errors are positively correlated with calculation errors. Consequently, we observe that the 14-qubit quantum computer, on average, is more prone to errors than the 5-qubit quantum computer.
Distributed quantum computation has gained extensive attention since small-qubit quantum computers seem to be built more practically in the noisy intermediate-scale quantum (NISQ) era. In this paper, we give a distributed Bernstein-Vazirani algorithm (DBVA) with ttt computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. Though the designing techniques are simple in the light of BV algorithm, Grover's algorithm, the improved Grover's algorithm by Long, and the distributed Grover's algorithm by Qiu et al, in comparison to BV algorithm, the circuit depth of DBVA is not greater than 2max(n0,n1,⋯ ,nt−1)+32^{\text{max}(n_0, n_1, \cdots, n_{t-1})}+32max(n0​,n1​,⋯,nt−1​)+3 instead of 2n+32^{n}+32n+3, and the circuit depth of DEGA is 8(n mod 2)+98(n~\text{mod}~2)+98(n mod 2)+9, which is less than the circuit depth of Grover's algorithm, 1+8⌊π42n⌋1 + 8\left\lfloor \fracπ{4}\sqrt{2^n} \right\rfloor1+8⌊4π​2n​⌋. In particular, we provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods. By simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithm has superiority of resisting noise.