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:0811.1359 · AIP conference proceedings

Discrimination of Unitary Transformations and Quantum Algorithms

David C. Collins, Alexander I. Lvovsky

Published Jan 1, 2009• 0 citations
arXivHTMLPDF

Abstract

Quantum algorithms are typically understood in terms of the evolution of a multi-qubit quantum system under a prescribed sequence of unitary transformations. The input to the algorithm prescribes some of the unitary transformations in the sequence with others remaining fixed. For oracle query algorithms, the input determines the oracle unitary transformation. Such algorithms can be regarded as devices for discriminating amongst a set of unitary transformations. The question arises: "Given a set of known oracle unitary transformations, to what extent is it possible to discriminate amongst them?" We investigate this for the Deutsch-Jozsa problem. The task of discriminating amongst the admissible oracle unitary transformations results in an exhaustive collection of algorithms which can solve the problem with certainty.

DOI
10.1063/1.3131360

Related papers

Discrimination of unitary transformations in the Deutsch-Jozsa algorithm: Implications for thermal-equilibrium-ensemble implementations

David C. Collins

A general framework for regarding oracle-assisted quantum algorithms as tools for discriminating among unitary transformations is described. This framework is applied to the Deutsch-Jozsa problem and all possible quantum algorithms which solve the problem with certainty using oracle unitaries in a particular form are derived. It is also used to show that any quantum algorithm that solves the Deutsch-Jozsa problem starting with a quantum system in a particular class of initial, thermal equilibrium-based states of the type encountered in solution-state NMR can only succeed with greater probability than a classical algorithm when the problem size $n$ exceeds $~{10}^{5}.$

arXiv:1002.4227•Physical Review A•May 19, 2010•5 citations

Unambiguous discrimination among oracle operators

Anthony Chefles, Akira Kitagawa, Masahiro Takeoka +2 more

We address the problem of unambiguous discrimination among oracle operators. The general theory of unambiguous discrimination among unitary operators is extended with this application in mind. We prove that entanglement with an ancilla cannot assist any discrimination strategy for commuting unitary operators. We also obtain a simple, practical test for the unambiguous distinguishability of an arbitrary set of unitary operators on a given system. Using this result, we prove that the unambiguous distinguishability criterion is the same for both standard and minimal oracle operators. We then show that, except in certain trivial cases, unambiguous discrimination among all standard oracle operators corresponding to integer functions with fixed domain and range is impossible. However, we find that it is possible to unambiguously discriminate among the Grover oracle operators corresponding to an arbitrarily large unsorted database. The unambiguous distinguishability of standard oracle operators corresponding to totally indistinguishable functions, which possess a strong form of classical indistinguishability, is analysed. We prove that these operators are not unambiguously distinguishable for any finite set of totally indistinguishable functions on a Boolean domain and with arbitrary fixed range. Sets of such functions on a larger domain can have unambiguously distinguishable standard oracle operators, and we provide a complete analysis of the simplest case, that of four functions. We also examine the possibility of unambiguous oracle operator discrimination with multiple parallel calls and investigate an intriguing unitary superoperator transformation between standard and entanglement-assisted minimal oracle operators.

arXiv:quant-ph/0702245•Journal of Physics A Mathematical and Theoretical•Aug 1, 2007•40 citations

Quantum-state filtering applied to the discrimination of Boolean functions

János A. Bergou, Mark S. Hillery

Quantum-state filtering is a variant of the unambiguous state discrimination problem: the states are grouped in sets and we want to determine to which particular set a given input state belongs. The simplest case, when the $N$ given states are divided into two subsets and the first set consists of one state only while the second consists of all of the remaining states, is termed quantum-state filtering. We derived previously the optimal strategy for the case of $N$ nonorthogonal states, ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$, for distinguishing $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. In a previous paper [Phys. Rev. Lett. 90, 257901 (2003)], we sketched an appplication of the results to probabilistic quantum algorithms. Here we fill the gaps and give the complete derivation of the probabilstic quantum algorithm that can optimally distinguish between two classes of Boolean functions, that of the balanced functions and that of the biased functions. The algorithm is probabilistic, it fails sometimes but when it does it lets us know that it did. Our approach can be considered as a generalization of the Deutsch-Jozsa algorithm that was developed for the discrimination of balanced and constant Boolean functions.

arXiv:quant-ph/0507092•Physical Review A•Jul 5, 2005•9 citations

Comparing two quantum oracles using the Deutsch–Jozsa algorithm

Attila Kiss, Krisztián Varga

There are a lot of articles about quantum algorithms, which involve querying a black box function, often called an oracle.This paper proposes a way to combine two oracles and to determine how similar they are using the Deutsch-Jozsa algorithm.In this case being similar means, that the sets of marked states have just a few ones outside of their intersection.The new quantum algorithm is compared to its classical counterparts and a detailed analysis shows when it will outperform them.

Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatorica•Jan 1, 2020•1 citation

Single-Query Exact Discrimination of Phase-Modified Permutation Oracles

Owen Root

Abstract I consider a promise problem for an unknown unitary acting on an \((n)\)-qubit register. The oracle is promised to implement either a fixed permutation of computational basis states or the same permutation accompanied by a conditional sign change determined by a designated input qubit. I show that the two cases can be distinguished exactly with a single query to the oracle and a measurement on only one qubit, and that the query complexity of this task is exactly one. The protocol uses no ancilla qubits and requires only \((n+1)\) Hadamard gates in addition to the oracle call. The promise is intrinsically quantum because the two cases differ only through relative phases. MSC Classification: 81P68 , 68Q12

•Oct 14, 2026•0 citations

A Generalization of the Deutsch-Jozsa Algorithm to Multi-Valued Quantum Logic

Yale Fan

We generalize the binary Deutsch-Jozsa algorithm to n- valued logic using the quantum Fourier transform. Our algorithm is not only able to distinguish between constant and balanced Boolean functions in a single query, but can also find closed expressions for classes of affine functions in quantum oracles, accurate to a constant term.

arXiv:0809.0932•IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2007•26 citations
Quantum algorithms are typically understood in terms of the evolution of a multi-qubit quantum system under a prescribed sequence of unitary transformations. The input to the algorithm prescribes some of the unitary transformations in the sequence with others remaining fixed. For oracle query algorithms, the input determines the oracle unitary transformation. Such algorithms can be regarded as devices for discriminating amongst a set of unitary transformations. The question arises: "Given a set of known oracle unitary transformations, to what extent is it possible to discriminate amongst them?" We investigate this for the Deutsch-Jozsa problem. The task of discriminating amongst the admissible oracle unitary transformations results in an exhaustive collection of algorithms which can solve the problem with certainty.
A general framework for regarding oracle-assisted quantum algorithms as tools for discriminating among unitary transformations is described. This framework is applied to the Deutsch-Jozsa problem and all possible quantum algorithms which solve the problem with certainty using oracle unitaries in a particular form are derived. It is also used to show that any quantum algorithm that solves the Deutsch-Jozsa problem starting with a quantum system in a particular class of initial, thermal equilibrium-based states of the type encountered in solution-state NMR can only succeed with greater probability than a classical algorithm when the problem size nnn exceeds  105.~{10}^{5}. 105.
We address the problem of unambiguous discrimination among oracle operators. The general theory of unambiguous discrimination among unitary operators is extended with this application in mind. We prove that entanglement with an ancilla cannot assist any discrimination strategy for commuting unitary operators. We also obtain a simple, practical test for the unambiguous distinguishability of an arbitrary set of unitary operators on a given system. Using this result, we prove that the unambiguous distinguishability criterion is the same for both standard and minimal oracle operators. We then show that, except in certain trivial cases, unambiguous discrimination among all standard oracle operators corresponding to integer functions with fixed domain and range is impossible. However, we find that it is possible to unambiguously discriminate among the Grover oracle operators corresponding to an arbitrarily large unsorted database. The unambiguous distinguishability of standard oracle operators corresponding to totally indistinguishable functions, which possess a strong form of classical indistinguishability, is analysed. We prove that these operators are not unambiguously distinguishable for any finite set of totally indistinguishable functions on a Boolean domain and with arbitrary fixed range. Sets of such functions on a larger domain can have unambiguously distinguishable standard oracle operators, and we provide a complete analysis of the simplest case, that of four functions. We also examine the possibility of unambiguous oracle operator discrimination with multiple parallel calls and investigate an intriguing unitary superoperator transformation between standard and entanglement-assisted minimal oracle operators.
Quantum-state filtering is a variant of the unambiguous state discrimination problem: the states are grouped in sets and we want to determine to which particular set a given input state belongs. The simplest case, when the NNN given states are divided into two subsets and the first set consists of one state only while the second consists of all of the remaining states, is termed quantum-state filtering. We derived previously the optimal strategy for the case of NNN nonorthogonal states, ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$, for distinguishing $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. In a previous paper [Phys. Rev. Lett. 90, 257901 (2003)], we sketched an appplication of the results to probabilistic quantum algorithms. Here we fill the gaps and give the complete derivation of the probabilstic quantum algorithm that can optimally distinguish between two classes of Boolean functions, that of the balanced functions and that of the biased functions. The algorithm is probabilistic, it fails sometimes but when it does it lets us know that it did. Our approach can be considered as a generalization of the Deutsch-Jozsa algorithm that was developed for the discrimination of balanced and constant Boolean functions.
Abstract I consider a promise problem for an unknown unitary acting on an (n)(n)(n)-qubit register. The oracle is promised to implement either a fixed permutation of computational basis states or the same permutation accompanied by a conditional sign change determined by a designated input qubit. I show that the two cases can be distinguished exactly with a single query to the oracle and a measurement on only one qubit, and that the query complexity of this task is exactly one. The protocol uses no ancilla qubits and requires only (n+1)(n+1)(n+1) Hadamard gates in addition to the oracle call. The promise is intrinsically quantum because the two cases differ only through relative phases. MSC Classification: 81P68 , 68Q12