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

Quantum Information and Computation

Quantum advantage without entanglement

KenigsbergDan, MorTal, RatsabyGil

Published Nov 1, 2006• 0 citations
OpenAlex

Abstract

We study the advantage of pure-state quantum computation without entanglement over classical computation. For the Deutsch-Jozsa algorithm we present the maximal subproblem that can be solved withou...

Related papers

Quantum advantage without entanglement

Dan Kenigsberg, Tal Mor, Gil Ratsaby

We study the advantage of pure-state quantum computation without entanglement over classical computation. For the Deutsch-Jozsa algorithm we present the maximal subproblem that can be solved without entanglement, and show that the algorithm still has an advantage over the classical ones. We further show that this subproblem is of greater significance, by proving that it contains all the Boolean functions whose quantum phase-oracle is non-entangling. For Simon's and Grover's algorithms we provide simple proofs that no non-trivial subproblems can be solved by these algorithms without entanglement.

arXiv:quant-ph/0511272•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 18, 2005•3 citations

Quantum advantage without entanglement

Dan Kenigsberg, A. Mor, Gil Ratsaby

We study the advantage of pure-state quantum computation without entanglement over classical computation. For the Deutsch-Jozsa algorithm we present the \emph{maximal} subproblem that can be solved without entanglement, and show that the algorithm still has an advantage over the classical ones. We further show that this subproblem is of greater significance, by proving that it contains all the Boolean functions whose quantum phase-oracle is non-entangling. For Simon's and Grover's algorithms we provide simple proofs that no non-trivial subproblems can be solved by these algorithms without entanglement.

Quantum Information and Computation•Nov 1, 2006•27 citations

An elementary derivation of the Deutsch-Jozsa algorithm

Neda Amin, Patrick Labelle

Quantum computing takes fully advantage of the superposition principle to increase greatly (even exponentially) the speed of calculations, relative to the classical approach. The Deutsch-Jozsa algorithm is the simplest quantum algorithm illustrating this power. Unfortunately, the standard derivation involves several ingenious steps which usually leave students feeling that they could never have figured out the algorithm by themselves. We present here a different formulation of the problem which allows students to derive the algorithm using only basic knowledge of quantum mechanics and linear algebra.

arXiv:0810.2285•Oct 13, 2008•0 citations

De-quantisation in Quantum Computation

Alastair A. Abbott

Quantum computation has shown much promise at providing, at least in some cases, a significant advantage over classical computation. However, the nature of quantum computation is still far from being well understood. In order to develop quantum algorithms effectively, it is important to understand the true nature of the differences between classical and quantum computation. We investigate these differences more closely by looking at de-quantising quantum algorithms into classical counterparts which retain the benefit provided by, and thought to be intrinsic to, the quantum algorithms. We extend a previous de-quantisation of Deutsch’s problem to show that in some situations the quantum algorithm solving the Deutsch-Jozsa problem can be de-quantised into an equivalent classical one. We quantify the entanglement in this problem and show that the inability to easily extend the de-quantisation to the general case is a result of the entanglement destroying the concise classical state description needed to de-quantise such a black-box algorithm. We further show that the quantum Fourier transform, an important process in many quantum algorithms, in its standard form is de-quantisable. This highlights key misconceptions about both the quantum Fourier transform and quantum computation itself. In such cases it is the linearity of quantum mechanics which allows constructing quantum algorithms which offer advantage over classical algorithms. The careful investigation of de-quantisation in relation to these problems allows a deeper insight into the nature of quantum computation.

•Jan 1, 2009•1 citation

Deutsch and Jozsa's Algorithm Revisited

J. Cooper

A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed

arXiv:quant-ph/0603231•Mar 27, 2006•0 citations

Quantum Advantage with Deutsch-Jozsa, Bernstein-Vazirani, and Simon’s Algorithms

Vladimir Silva

In this chapter, we study three algorithms of little practical use but important because they were the first to show that quantum computers can solve problems significantly faster than classical ones. Consider the time complexities O(n) for the algorithms: classical vs. quantum in Table 9-1 (where n is the size of the input).

Apress eBooks•Dec 18, 2023•0 citations
We study the advantage of pure-state quantum computation without entanglement over classical computation. For the Deutsch-Jozsa algorithm we present the maximal subproblem that can be solved without entanglement, and show that the algorithm still has an advantage over the classical ones. We further show that this subproblem is of greater significance, by proving that it contains all the Boolean functions whose quantum phase-oracle is non-entangling. For Simon's and Grover's algorithms we provide simple proofs that no non-trivial subproblems can be solved by these algorithms without entanglement.
We study the advantage of pure-state quantum computation without entanglement over classical computation. For the Deutsch-Jozsa algorithm we present the \emph{maximal} subproblem that can be solved without entanglement, and show that the algorithm still has an advantage over the classical ones. We further show that this subproblem is of greater significance, by proving that it contains all the Boolean functions whose quantum phase-oracle is non-entangling. For Simon's and Grover's algorithms we provide simple proofs that no non-trivial subproblems can be solved by these algorithms without entanglement.
Quantum computing takes fully advantage of the superposition principle to increase greatly (even exponentially) the speed of calculations, relative to the classical approach. The Deutsch-Jozsa algorithm is the simplest quantum algorithm illustrating this power. Unfortunately, the standard derivation involves several ingenious steps which usually leave students feeling that they could never have figured out the algorithm by themselves. We present here a different formulation of the problem which allows students to derive the algorithm using only basic knowledge of quantum mechanics and linear algebra.
Quantum computation has shown much promise at providing, at least in some cases, a significant advantage over classical computation. However, the nature of quantum computation is still far from being well understood. In order to develop quantum algorithms effectively, it is important to understand the true nature of the differences between classical and quantum computation. We investigate these differences more closely by looking at de-quantising quantum algorithms into classical counterparts which retain the benefit provided by, and thought to be intrinsic to, the quantum algorithms. We extend a previous de-quantisation of Deutsch’s problem to show that in some situations the quantum algorithm solving the Deutsch-Jozsa problem can be de-quantised into an equivalent classical one. We quantify the entanglement in this problem and show that the inability to easily extend the de-quantisation to the general case is a result of the entanglement destroying the concise classical state description needed to de-quantise such a black-box algorithm. We further show that the quantum Fourier transform, an important process in many quantum algorithms, in its standard form is de-quantisable. This highlights key misconceptions about both the quantum Fourier transform and quantum computation itself. In such cases it is the linearity of quantum mechanics which allows constructing quantum algorithms which offer advantage over classical algorithms. The careful investigation of de-quantisation in relation to these problems allows a deeper insight into the nature of quantum computation.