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:2104.07817 · Physical Review A

Quantum advantage and noise reduction in distributed quantum computing

J. E. Avron, Ofer Casper, Ilan Rozen

Published Nov 5, 2021• 49 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.104.052404

Related papers

Distributed quantum algorithm for Simon's problem

Jiawei Tan, Ligang Xiao, Daowen Qiu +2 more

Limited by today's physical devices, quantum circuits with a long depth are usually noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we study Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The algorithm proposed by us has the advantage of exponential acceleration compared with classical distributed computing and has the advantage of square acceleration compared with the best distributed quantum algorithm proposed before in query complexity. In particular, the previous distributed quantum algorithm for Simon's problem cannot be extended to the case of more than two computing nodes (i.e., two subproblems), but our distributed quantum algorithm can be extended to the case of multiple computing nodes (i.e., multiple subproblems).

arXiv:2204.11388•Physical Review A•Sep 13, 2022•31 citations

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

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

uantum Advantage and the Evolution of Query Complexity a Critical Analysis of the Deutsch, Deutsch–Jozsa, and Simon Algorithms

Medak Srinivas

Quantum computation transformed our thinking about computational complexity by showing that quantum mechanical principles can be used to reduce the number of queries needed to solve some problems. The work constitutes a critical analysis of the evolution of the query complexity through three fundamental quantum algo rithms: the Deutsch algorithm, the Deutsch–Jozsa algorithm and Simon’s algorithm. Together, these algorithms illustrate the emergence of quantum advantage where quantum systems outperform classical deterministic and probabilistic approaches by exploiting superposition, interference, entanglement and unitary evolution.The study begins with the Deutsch algorithm, the first demonstration that a quantum computer can compute a global property of a Boolean function with fewer oracle queries than any deterministic classical algorithm. We further extend the analysis to the Deutsch–Jozsa algorithm, which generalizes this speedup to the exponential level by distinguishing between balanced and constant Boolean functions with one quantum query. Then we study Simon’s Algorithm, a milestone that achieved an exponential separation between classical randomized and quantum query complexity. The groundwork for many later advances, such as Shor’s algorithm for factoring integers, was established by this body of work. The discussion continues with an emphasis on Linear Algebra and the use of Hilbert spaces, Tensor Products, Unitary Transformations, and Fourier based interference methods. As the report describes, significant advancements toward reducing the time it takes for quantum systems to perform calculations are made possible through use of Oracle construction, Spectral Decomposition, and Mea surement Theory. This comparative analysis explores the use of computational queries in deterministic, probabilistic, and quan tum models while examining the transition from classical decision tree complexities into quantum computation paradigms. Ultimately, the results of this analysis show that the early quantum algorithms must be recognized not merely as isolated computational oddities, but rather as crucial components of the development of quantum information sci ence. They provided a conceptual and mathematical framework for the modern understanding of what constitutes a quantum advantage; Moreover, they also provide valuable insight into how quantum mechanical systems influ ence both computational efficiency and complexity theory, specifically as well as future information processing system design.

Iterative International Publishers eBooks•May 1, 2026•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•29 citations
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.
Limited by today's physical devices, quantum circuits with a long depth are usually noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we study Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The algorithm proposed by us has the advantage of exponential acceleration compared with classical distributed computing and has the advantage of square acceleration compared with the best distributed quantum algorithm proposed before in query complexity. In particular, the previous distributed quantum algorithm for Simon's problem cannot be extended to the case of more than two computing nodes (i.e., two subproblems), but our distributed quantum algorithm can be extended to the case of multiple computing nodes (i.e., multiple subproblems).
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 computation transformed our thinking about computational complexity by showing that quantum mechanical principles can be used to reduce the number of queries needed to solve some problems. The work constitutes a critical analysis of the evolution of the query complexity through three fundamental quantum algo rithms: the Deutsch algorithm, the Deutsch–Jozsa algorithm and Simon’s algorithm. Together, these algorithms illustrate the emergence of quantum advantage where quantum systems outperform classical deterministic and probabilistic approaches by exploiting superposition, interference, entanglement and unitary evolution.The study begins with the Deutsch algorithm, the first demonstration that a quantum computer can compute a global property of a Boolean function with fewer oracle queries than any deterministic classical algorithm. We further extend the analysis to the Deutsch–Jozsa algorithm, which generalizes this speedup to the exponential level by distinguishing between balanced and constant Boolean functions with one quantum query. Then we study Simon’s Algorithm, a milestone that achieved an exponential separation between classical randomized and quantum query complexity. The groundwork for many later advances, such as Shor’s algorithm for factoring integers, was established by this body of work. The discussion continues with an emphasis on Linear Algebra and the use of Hilbert spaces, Tensor Products, Unitary Transformations, and Fourier based interference methods. As the report describes, significant advancements toward reducing the time it takes for quantum systems to perform calculations are made possible through use of Oracle construction, Spectral Decomposition, and Mea surement Theory. This comparative analysis explores the use of computational queries in deterministic, probabilistic, and quan tum models while examining the transition from classical decision tree complexities into quantum computation paradigms. Ultimately, the results of this analysis show that the early quantum algorithms must be recognized not merely as isolated computational oddities, but rather as crucial components of the development of quantum information sci ence. They provided a conceptual and mathematical framework for the modern understanding of what constitutes a quantum advantage; Moreover, they also provide valuable insight into how quantum mechanical systems influ ence both computational efficiency and complexity theory, specifically as well as future information processing system design.
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.