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

Dan Kenigsberg, A. Mor, Gil Ratsaby

Published Nov 1, 2006• 29 citations
Publisher

Abstract

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.

DOI
10.26421/qic6.7-4

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

Quantum advantage and noise reduction in distributed quantum computing

J. E. Avron, Ofer Casper, Ilan Rozen

Distributed quantum computing can provide substantial noise reduction due to shallower circuits. An experiment illustrates the advantages in the case of a Grover search. This motivates study of the quantum advantage of the distributed version of the Simon and Deutsch-Jozsa algorithms. We show that the distributed Simon algorithm retains the exponential advantage, but the complexity deteriorates from $O(n)$ to $O({n}^{2})$, where $n={log}_{2}(N)$. The distributed Deutsch-Jozsa algorithm deteriorates to being probabilistic but retains a quantum advantage over classical random sampling.

arXiv:2104.07817•Physical Review A•Nov 5, 2021•55 citations

Quantum Simulation Logic, Oracles, and the Quantum Advantage

Niklas Johansson, Jan-Åke Larsson

Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, such as the Deutsch-Jozsa and Simon's algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shor's algorithm for integer factorization.

arXiv:1905.05082•Entropy•Aug 15, 2019•25 citations

An introduction to quantum: computing, communication complexity protocols, nonlocality and graph parameters

Lucas Silva Arenstein

What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.

•Dec 12, 2022•0 citations

Efficient classical simulation of the Deutsch–Jozsa and Simon’s algorithms

Niklas Johansson, Jan-Åke Larsson

A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.

arXiv:1508.05027•Quantum Information Processing•Aug 12, 2017•36 citations
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.
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.
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.
Distributed quantum computing can provide substantial noise reduction due to shallower circuits. An experiment illustrates the advantages in the case of a Grover search. This motivates study of the quantum advantage of the distributed version of the Simon and Deutsch-Jozsa algorithms. We show that the distributed Simon algorithm retains the exponential advantage, but the complexity deteriorates from O(n)O(n)O(n) to O(n2)O({n}^{2})O(n2), where n=log2(N)n={log}_{2}(N)n=log2​(N). The distributed Deutsch-Jozsa algorithm deteriorates to being probabilistic but retains a quantum advantage over classical random sampling.
Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, such as the Deutsch-Jozsa and Simon's algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shor's algorithm for integer factorization.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.
A long-standing aim of quantum information research is to understand what gives quantum computers their advantage. This requires separating problems that need genuinely quantum resources from those for which classical resources are enough. Two examples of quantum speed-up are the Deutsch–Jozsa and Simon’s problem, both efficiently solvable on a quantum Turing machine, and both believed to lack efficient classical solutions. Here we present a framework that can simulate both quantum algorithms efficiently, solving the Deutsch–Jozsa problem with probability 1 using only one oracle query, and Simon’s problem using linearly many oracle queries, just as expected of an ideal quantum computer. The presented simulation framework is in turn efficiently simulatable in a classical probabilistic Turing machine. This shows that the Deutsch–Jozsa and Simon’s problem do not require any genuinely quantum resources, and that the quantum algorithms show no speed-up when compared with their corresponding classical simulation. Finally, this gives insight into what properties are needed in the two algorithms and calls for further study of oracle separation between quantum and classical computation.