© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal 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• 0 citations

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•2 citations

A Generalization of Bernstein-Vazirani Algorithm to Qudit Systems

R Narayanan Krishna, Vishesh Makwana, Ananda Padhmanabhan Suresh

A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.

arXiv:1609.03185•Sep 11, 2016•5 citations

Optical implementations, oracle equivalence, and the Bernstein-Vazirani algorithm

Arvind, Gurpreet Kaur, Geetu Narang

We describe a new implementation of the Bernstein-Vazirani algorithm that relies on the fact that the polarization states of classical light beams can be cloned. We explore the possibility of computing with waves and discuss a classical optical model capable of implementing any algorithm (on n qubits) that does not involve entanglement. The Bernstein-Vazirani algorithm (with a suitably modified oracle), wherein a hidden n-bit vector is discovered by one oracle query as against n oracle queries required classically, belongs to this category. In our scheme, the modified oracle is also capable of computing f(x) for a given x, which is not possible with earlier versions used in recent NMR and optics implementations of the algorithm.

arXiv:quant-ph/0605092•Journal of the Optical Society of America B•Jan 26, 2007•12 citations

Practical Experience with IBM Q Quantum Computer: Bernstein–Vazirani Algorithm

Mikhail Pavlov

Abstract This study presents practical experience implementing the Bernstein–Vazirani algorithm on the IBM Q quantum computing platform, focusing on energy-efficient and reversible computation guided by Landauer’s principle. The work highlights the role of fundamental quantum logic gates—including CNOT, NOT, CCNOT, OR, and XOR—in constructing scalable, reversible circuits. By applying these principles, the Bernstein–Vazirani algorithm demonstrates an efficient solution to the problem of determining a hidden binary vector with a minimal number of queries, showcasing the potential for quantum computational speedup and optimization of information processing. The research emphasizes the importance of reversible quantum operations in improving computational efficiency and expanding the capabilities of modern quantum systems.

•Mar 4, 2026•0 citations

Quantum Query Algorithms

Walid E. Gomaa

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.

•Nov 19, 2025•0 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

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.

A quantum algorithm to solve the parity problem is better than its most efficient classical counter- part with a separation that is polynomial in the number of queries. This was shown by E. Bernstein and U. Vazirani and was one of the earliest indications that the quantum information processing can outperform the classical one by a significant margin. The problem and its solution both is usually stated for a 2-level system since we generally work with bits/qubits. However, many works have been done generalizing known quantum computing techniques to higher level systems. Following this, we look at a generalization of the Bernstein-Vazirani algorithm implemented on a general qudit system.

We describe a new implementation of the Bernstein-Vazirani algorithm that relies on the fact that the polarization states of classical light beams can be cloned. We explore the possibility of computing with waves and discuss a classical optical model capable of implementing any algorithm (on n qubits) that does not involve entanglement. The Bernstein-Vazirani algorithm (with a suitably modified oracle), wherein a hidden n-bit vector is discovered by one oracle query as against n oracle queries required classically, belongs to this category. In our scheme, the modified oracle is also capable of computing f(x) for a given x, which is not possible with earlier versions used in recent NMR and optics implementations of the algorithm.

Abstract This study presents practical experience implementing the Bernstein–Vazirani algorithm on the IBM Q quantum computing platform, focusing on energy-efficient and reversible computation guided by Landauer’s principle. The work highlights the role of fundamental quantum logic gates—including CNOT, NOT, CCNOT, OR, and XOR—in constructing scalable, reversible circuits. By applying these principles, the Bernstein–Vazirani algorithm demonstrates an efficient solution to the problem of determining a hidden binary vector with a minimal number of queries, showcasing the potential for quantum computational speedup and optimization of information processing. The research emphasizes the importance of reversible quantum operations in improving computational efficiency and expanding the capabilities of modern quantum systems.

This presentation gives a comprehensive overview of quantum query algorithms, beginning with an introduction to the query model of computation where input is accessed via an oracle function. It then details several foundational quantum algorithms that demonstrate a quantum advantage over classical approaches: Deutsch's problem is solved with a single query using phase kickback to determine if a function is constant or balanced; the Deutsch-Jozsa algorithm extends this to n-bit inputs, efficiently distinguishing constant from balanced functions with one query versus an exponential need classically; the Bernstein-Vazirani algorithm identifies a hidden string with one query, outperforming classical linear requirements; and Simon's algorithm, which finds a hidden period in a two-to-one function with a linear number of queries, showcases an exponential speedup over the best classical probabilistic algorithms.