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

Mysteries, Puzzles, and Paradoxes in Quantum Mechanics

Some extensions of the Deutsch problem

A. M. Grassi, G. Strini

Published Jan 1, 1999• 0 citations
Publisher

Abstract

In the search for useful trick for quantum algorithms, a study has been made on the possible global properties of the standard logic functions of two and more logical variables. This gives an algorithm exponentially faster than the corresponding classical one.
DOI
10.1063/1.57881

Related papers

An Extension of the Deutsch-Jozsa Algorithm to Arbitrary Qudits

Peter Marttala

Recent advances in quantum computational science promise substantial improvements in the speed with which certain classes of problems can be computed. Various algorithms that utilize the distinctively non-classical characteristics of quantum mechanics have been formulated to take advantage of this promising new approach to computation. One such algorithm was formulated by David Deutsch and Richard Jozsa. By measuring the output of a quantum network that implements this algorithm, it is possible to determine with N – 1 measurements certain global properties of a function f(x), where N is the number of network inputs. Classically, it may not be possible to determine these same properties without evaluating f(x) a number of times that rises exponentially as N increases. Hitherto, the potential power of this algorithm has been explored in the context of qubits, the quantum computational analogue of classical bits. However, just as one can conceive of classical computation in the context of non-binary logic, such as ternary or quaternary logic, so also can one conceive of corresponding higher-order quantum computational equivalents.This thesis investigates the behaviour of the Deutsch-Jozsa algorithm in the context of these higher-order quantum computational forms of logic and explores potential applications for this algorithm. An important conclusion reached is that, not only can the Deutsch-Jozsa algorithm’s known computational advantages be formulated in more general terms, but also a new algorithmic property is revealed with potential practical applications.

•Jan 1, 2007•0 citations

SOME UNSOLVED PROBLEMS IN QUANTUM LOGICS

Stanley Gudder

Elsevier eBooks•Jan 1, 1978•13 citations

Noise-based Logic versus Quantum Supremacy

László B. Kish

Quantum Supremacy is an expression coined to indicate that there are some hard computational problems that quantum computers can solve exponentially faster than a classical-physical Turing machine (that is, a digital computer). Noise-based Logic (NBL) is a deterministic computation scheme that utilizes a digital computer and a physical true random number generator (TRNG). Recently, several computational problems have been identified where NBL also deterministically offered an exponential speedup compared to a digital computer. In the case of phonebook search, at proper conditions, NBL can even be exponentially faster than Grover's quantum algorithm that offers only a polynomial speedup compared to a digital computer. The newest result is the implementation of the Deutsch-Jozsa problem in NBL. The Deutsch-Jozsa quantum algorithm was historically the first one that was able to offer quantum supremacy. NBL offers the same speedup class. Open philosophical questions emerge about the role of true randomness in the speedup.

IEEE International Symposium on Computational Intelligence and Informatics (CINTI)•Nov 21, 2022•0 citations

Quantum Algorithm for Evaluating Two of Logical Functions Simultaneously

Koji Nagata, Tadao Nakamura

International Journal of Theoretical Physics•May 27, 2020•1 citation

A quantum algorithm based on entanglement measure for classifying Boolean multivariate function into novel hidden classes

Mohammed Zidan, Abdel‐Haleem Abdel‐Aty, Duc Manh Nguyen +4 more

In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.

Results in Physics•Aug 9, 2019•58 citations

Quantum logic gate construction and quantum algorithms

Xinlan Zhou

•Jan 1, 2002•0 citations
Recent advances in quantum computational science promise substantial improvements in the speed with which certain classes of problems can be computed. Various algorithms that utilize the distinctively non-classical characteristics of quantum mechanics have been formulated to take advantage of this promising new approach to computation. One such algorithm was formulated by David Deutsch and Richard Jozsa. By measuring the output of a quantum network that implements this algorithm, it is possible to determine with N – 1 measurements certain global properties of a function f(x), where N is the number of network inputs. Classically, it may not be possible to determine these same properties without evaluating f(x) a number of times that rises exponentially as N increases. Hitherto, the potential power of this algorithm has been explored in the context of qubits, the quantum computational analogue of classical bits. However, just as one can conceive of classical computation in the context of non-binary logic, such as ternary or quaternary logic, so also can one conceive of corresponding higher-order quantum computational equivalents.This thesis investigates the behaviour of the Deutsch-Jozsa algorithm in the context of these higher-order quantum computational forms of logic and explores potential applications for this algorithm. An important conclusion reached is that, not only can the Deutsch-Jozsa algorithm’s known computational advantages be formulated in more general terms, but also a new algorithmic property is revealed with potential practical applications.
Quantum Supremacy is an expression coined to indicate that there are some hard computational problems that quantum computers can solve exponentially faster than a classical-physical Turing machine (that is, a digital computer). Noise-based Logic (NBL) is a deterministic computation scheme that utilizes a digital computer and a physical true random number generator (TRNG). Recently, several computational problems have been identified where NBL also deterministically offered an exponential speedup compared to a digital computer. In the case of phonebook search, at proper conditions, NBL can even be exponentially faster than Grover's quantum algorithm that offers only a polynomial speedup compared to a digital computer. The newest result is the implementation of the Deutsch-Jozsa problem in NBL. The Deutsch-Jozsa quantum algorithm was historically the first one that was able to offer quantum supremacy. NBL offers the same speedup class. Open philosophical questions emerge about the role of true randomness in the speedup.
In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.