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

A quantum algorithm for counting zero-crossings

Shukla, Alok

Published Dec 21, 2022• 5 citations
arXivHTMLPDF

Abstract

We present a zero-crossings counting problem that is a generalization of the Bernstein-Vazirani problem. The goal of this problem is to count the number of zero-crossings (or sign changes) in a special type of sequence S, whose definition depends upon a secret string. A quantum algorithm is presented to solve this problem. The proposed quantum algorithm requires only one oracle query to solve the problem, whereas a classical algorithm would need at least n oracle queries, where $2^n$ is the size of the sequence S. In addition to solving the zero-crossings counting problem, we also give a quantum circuit for performing the Walsh-Hadamard transforms in sequency ordering. The Walsh-Hadamard transform in sequency ordering is used in a wide range of scientific and engineering applications, including in digital signal and image processing. Therefore, the proposed quantum circuit for computing the Walsh-Hadamard transforms in sequency ordering may be helpful in quantum computing algorithms for applications for which the computation of the Walsh-Hadamard transform in sequency ordering is required.

DOI
10.48550/arxiv.2212.11814

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

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

Real Matrix Representations of Quantum Operators: An Introduction to Quantum Index Algebra

A. Yu. Volkov, G. A. Koroteev, Yu. S. Volkov

We introduce Quantum Index Algebra (QIA) as a finite, index-based algebraic framework for representing and manipulating quantum operators on Hilbert spaces of dimension $2^m$. In QIA, operators are expressed as structured combinations of basis elements indexed by Boolean codes, allowing products, commutators, and conjugations to be computed through finite rules on discrete indices rather than through dense matrix arithmetic. This representation unifies combinatorial index structure, explicit matrix realization, and transformation properties under Walsh-Hadamard-type transforms within a single formalism. Using QIA and its associated block-matrix realization, we reformulate the Bernstein-Vazirani hidden-string problem in its phase-oracle form entirely within a real, finite-dimensional algebraic setting. We show that, under structured oracle access, the QIA procedure reproduces the Bernstein-Vazirani algorithm exactly and achieves the same asymptotic query complexity and circuit depth as the standard quantum algorithm. In particular, the hidden string is recovered by symbolic manipulation of a sparse algebraic representation of the oracle rather than by numerical simulation of quantum amplitudes. Our results demonstrate that the apparent quantum speed-up in this setting is a consequence of operator structure rather than Hilbert-space dimensionality alone. QIA thus provides a precise language for separating genuinely quantum resources from those arising from algebraic and combinatorial structures and offers a new perspective on the classical simulability of structured quantum circuits.

quant-pharXiv:2512.19977•Dec 24, 2025•0 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•9 citations

Generalization of the Deutsch algorithm using two qudits

Jose Luis Cereceda

Deutsch's algorithm for two qubits (one control qubit plus one auxiliary qubit) is extended to two $d$-dimensional quantum systems or qudits for the case in which $d$ is equal to $2^n$, $n=1,2,...$ . This allows one to classify a certain oracle function by just one query, instead of the $2^{n-1}+1$ queries required by classical means. The given algorithm for two qudits also solves efficiently the Bernstein-Vazirani problem. Entanglement does not occur at any step of the computation.

arXiv:quant-ph/0407253•Jul 29, 2004•11 citations

Quantum parity algorithms as oracle calls, and application in Grover Database search

Magdi Z. Rashad

This paper discusses the determination of the parity of a string of N binary digits, the well-known problem in classical as well as quantum information processing.It can be formulated as an oracle problem.It has been established that quantum algorithms require at least N /2 oracle calls.We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required.

Advanced Computing An International Journal•Mar 31, 2012•0 citations
We present a zero-crossings counting problem that is a generalization of the Bernstein-Vazirani problem. The goal of this problem is to count the number of zero-crossings (or sign changes) in a special type of sequence S, whose definition depends upon a secret string. A quantum algorithm is presented to solve this problem. The proposed quantum algorithm requires only one oracle query to solve the problem, whereas a classical algorithm would need at least n oracle queries, where 2n2^n2n is the size of the sequence S. In addition to solving the zero-crossings counting problem, we also give a quantum circuit for performing the Walsh-Hadamard transforms in sequency ordering. The Walsh-Hadamard transform in sequency ordering is used in a wide range of scientific and engineering applications, including in digital signal and image processing. Therefore, the proposed quantum circuit for computing the Walsh-Hadamard transforms in sequency ordering may be helpful in quantum computing algorithms for applications for which the computation of the Walsh-Hadamard transform in sequency ordering is required.
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.
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.
We introduce Quantum Index Algebra (QIA) as a finite, index-based algebraic framework for representing and manipulating quantum operators on Hilbert spaces of dimension 2m2^m2m. In QIA, operators are expressed as structured combinations of basis elements indexed by Boolean codes, allowing products, commutators, and conjugations to be computed through finite rules on discrete indices rather than through dense matrix arithmetic. This representation unifies combinatorial index structure, explicit matrix realization, and transformation properties under Walsh-Hadamard-type transforms within a single formalism. Using QIA and its associated block-matrix realization, we reformulate the Bernstein-Vazirani hidden-string problem in its phase-oracle form entirely within a real, finite-dimensional algebraic setting. We show that, under structured oracle access, the QIA procedure reproduces the Bernstein-Vazirani algorithm exactly and achieves the same asymptotic query complexity and circuit depth as the standard quantum algorithm. In particular, the hidden string is recovered by symbolic manipulation of a sparse algebraic representation of the oracle rather than by numerical simulation of quantum amplitudes. Our results demonstrate that the apparent quantum speed-up in this setting is a consequence of operator structure rather than Hilbert-space dimensionality alone. QIA thus provides a precise language for separating genuinely quantum resources from those arising from algebraic and combinatorial structures and offers a new perspective on the classical simulability of structured quantum circuits.
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.
Deutsch's algorithm for two qubits (one control qubit plus one auxiliary qubit) is extended to two ddd-dimensional quantum systems or qudits for the case in which ddd is equal to 2n2^n2n, n=1,2,...n=1,2,...n=1,2,... . This allows one to classify a certain oracle function by just one query, instead of the 2n−1+12^{n-1}+12n−1+1 queries required by classical means. The given algorithm for two qudits also solves efficiently the Bernstein-Vazirani problem. Entanglement does not occur at any step of the computation.