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

Demonstration of the Essentiality of Entanglement in a Deutsch-like Quantum Algorithm

He-Liang Huang, Ashutosh Goswami, Wan‐Su Bao, Prasanta Kumar Panigrahi

Published Jun 28, 2017• 2 citations
arXivHTMLPDF

Abstract

Quantum algorithms could efficiently solve certain classically intractable problems by exploiting quantum parallelism. To date, whether the quantum entanglement is useful or not for quantum computing is still a question of debate. Here, we present a new quantum algorithm to show that entanglement could help to gain advantage over classical algorithm and even the quantum algorithm without entanglement. Furthermore, we implement experiments to demonstrate our proposed algorithm using superconducting qubits. Our results show the viability of the algorithm and suggest that entanglement is essential in getting quantum speedup for certain problems in quantum computing, which provide a reliable and clear guidance for developing useful quantum algorithms in future.

DOI
10.48550/arxiv.1706.09489

Related papers

Essentiality of Entanglement in a Quantum Algorithm

Ashutosh Goswami, Prasanta Kumar Panigrahi

Quantum algorithms utilize quantum parallelism or quantum coherence to solve certain problems more efficiently than the classical algorithms. Whether quantum entanglement is useful or not for quantum computation is a question of debate. Here, we present a new quantum algorithm, where entanglement is required to gain advantage over classical algorithms.

•Jun 28, 2017•1 citation

Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup

Michael E. Cuffaro

Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill \& Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.

•Dec 6, 2011•0 citations

Breaking Barriers: Unleashing the Power of Quantum Algorithms

Douha Jerbi

Quantum computing is a rapidly developing field with the potential to revolutionize our ability to solve certain computational problems . While classical computers operate using classical bits, quantum computers use quantum bits (qubits), which can exist in a superposition of states, allowing for parallel computations. The existence of quantum algorithms, which can solve certain problems exponentially faster than classical algorithms, is one of the most exciting aspects of quantum computing. These exotic algorithms are designed to take advantage of quantum mechanical properties such as entanglement and interference, and have the potential to transform a range of fields, including cryptography, optimization, and machine learning.

•Apr 29, 2023•0 citations

Breaking Barriers: Unleashing the Power of Quantum Algorithms

Douha Jerbi

Quantum computing is a rapidly developing field with the potential to revolutionize our ability to solve certain computational problems . While classical computers operate using classical bits, quantum computers use quantum bits (qubits), which can exist in a superposition of states, allowing for parallel computations. The existence of quantum algorithms, which can solve certain problems exponentially faster than classical algorithms, is one of the most exciting aspects of quantum computing. These exotic algorithms are designed to take advantage of quantum mechanical properties such as entanglement and interference, and have the potential to transform a range of fields, including cryptography, optimization, and machine learning.

•Apr 29, 2023•0 citations

Towards quantum advantage via topological data analysis

Casper Gyurik, Chris Cade, Vedran Dunjko

Even after decades of quantum computing development, examples of generally useful quantum algorithms with exponential speedups over classical counterparts are scarce. Recent progress in quantum algorithms for linear-algebra positioned quantum machine learning (QML) as a potential source of such useful exponential improvements. Yet, in an unexpected development, a recent series of "dequantization" results has equally rapidly removed the promise of exponential speedups for several QML algorithms. This raises the critical question whether exponential speedups of other linear-algebraic QML algorithms persist. In this paper, we study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We provide evidence that the problem solved by this algorithm is classically intractable by showing that its natural generalization is as hard as simulating the one clean qubit model – which is widely believed to require superpolynomial time on a classical computer – and is thus very likely immune to dequantizations. Based on this result, we provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis, along with complexity-theoretic evidence for their classical intractability. Furthermore, we analyze the suitability of the proposed quantum algorithms for near-term implementations. Our results provide a number of useful applications for full-blown, and restricted quantum computers with a guaranteed exponential speedup over classical methods, recovering some of the potential for linear-algebraic QML to become one of quantum computing's killer applications.

arXiv:2005.02607•Quantum•Nov 10, 2022•42 citations

Quantum Decoding Algorithms: Quantum Speedups in Optimization

Jan Ljubas, Tim Byrnes

Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection (OPI) problem, strong evidence exists to show that an superpolynomial speedup exists over the best classical methods in obtaining an approximate solution. In this review, we give a self-contained description of DQI and the necessary background to understand the algorithm. Specifically, we give the essentials of Galois fields, optimization problems such as max-LINSAT and OPI, and coding theory, followed by a step-by-step walkthrough of the quantum algorithm and its operating principle.

quant-pharXiv:2605.00312•May 4, 2026•0 citations
Quantum algorithms could efficiently solve certain classically intractable problems by exploiting quantum parallelism. To date, whether the quantum entanglement is useful or not for quantum computing is still a question of debate. Here, we present a new quantum algorithm to show that entanglement could help to gain advantage over classical algorithm and even the quantum algorithm without entanglement. Furthermore, we implement experiments to demonstrate our proposed algorithm using superconducting qubits. Our results show the viability of the algorithm and suggest that entanglement is essential in getting quantum speedup for certain problems in quantum computing, which provide a reliable and clear guidance for developing useful quantum algorithms in future.
Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill \& Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.
Quantum computing is a rapidly developing field with the potential to revolutionize our ability to solve certain computational problems . While classical computers operate using classical bits, quantum computers use quantum bits (qubits), which can exist in a superposition of states, allowing for parallel computations. The existence of quantum algorithms, which can solve certain problems exponentially faster than classical algorithms, is one of the most exciting aspects of quantum computing. These exotic algorithms are designed to take advantage of quantum mechanical properties such as entanglement and interference, and have the potential to transform a range of fields, including cryptography, optimization, and machine learning.
Quantum computing is a rapidly developing field with the potential to revolutionize our ability to solve certain computational problems . While classical computers operate using classical bits, quantum computers use quantum bits (qubits), which can exist in a superposition of states, allowing for parallel computations. The existence of quantum algorithms, which can solve certain problems exponentially faster than classical algorithms, is one of the most exciting aspects of quantum computing. These exotic algorithms are designed to take advantage of quantum mechanical properties such as entanglement and interference, and have the potential to transform a range of fields, including cryptography, optimization, and machine learning.
Even after decades of quantum computing development, examples of generally useful quantum algorithms with exponential speedups over classical counterparts are scarce. Recent progress in quantum algorithms for linear-algebra positioned quantum machine learning (QML) as a potential source of such useful exponential improvements. Yet, in an unexpected development, a recent series of "dequantization" results has equally rapidly removed the promise of exponential speedups for several QML algorithms. This raises the critical question whether exponential speedups of other linear-algebraic QML algorithms persist. In this paper, we study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We provide evidence that the problem solved by this algorithm is classically intractable by showing that its natural generalization is as hard as simulating the one clean qubit model – which is widely believed to require superpolynomial time on a classical computer – and is thus very likely immune to dequantizations. Based on this result, we provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis, along with complexity-theoretic evidence for their classical intractability. Furthermore, we analyze the suitability of the proposed quantum algorithms for near-term implementations. Our results provide a number of useful applications for full-blown, and restricted quantum computers with a guaranteed exponential speedup over classical methods, recovering some of the potential for linear-algebraic QML to become one of quantum computing's killer applications.
Attaining a quantum speedup in solving practically useful optimization problems has been one of the holy grails in the field of quantum computing. While prior approaches have demonstrated speedups for certain structured problem classes, establishing a clear and scalable advantage on broadly useful practical optimization problems remains challenging. Recently, a new approach to solving the max-LINSAT class of optimization problems has emerged, called Decoded Quantum Interferometry (DQI). In DQI, a combination of techniques rooted in (classical) coding theory and interferometry are used to obtain the solution of max-LINSAT. In the special problem instance of the optimal polynomial intersection (OPI) problem, strong evidence exists to show that an superpolynomial speedup exists over the best classical methods in obtaining an approximate solution. In this review, we give a self-contained description of DQI and the necessary background to understand the algorithm. Specifically, we give the essentials of Galois fields, optimization problems such as max-LINSAT and OPI, and coding theory, followed by a step-by-step walkthrough of the quantum algorithm and its operating principle.