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

Physics

Gaining a Quantum Advantage Sooner than Expected

Marric Stephens

Published Dec 10, 2020• 0 citations
Publisher

Abstract

For an important quantum many-body problem, a hybrid quantum-classical algorithm could outperform purely classical approaches using surprisingly few quantum resources.
DOI
10.1103/physics.13.s159

Related papers

A Preprocessing Perspective for Quantum Machine Learning Classification Advantage in Finance Using NISQ Algorithms

Javier Mancilla, Christophe Père

Quantum Machine Learning (QML) has not yet demonstrated extensively and clearly its advantages compared to the classical machine learning approach. So far, there are only specific cases where some quantum-inspired techniques have achieved small incremental advantages, and a few experimental cases in hybrid quantum computing are promising, considering a mid-term future (not taking into account the achievements purely associated with optimization using quantum-classical algorithms). The current quantum computers are noisy and have few qubits to test, making it difficult to demonstrate the current and potential quantum advantage of QML methods. This study shows that we can achieve better classical encoding and performance of quantum classifiers by using Linear Discriminant Analysis (LDA) during the data preprocessing step. As a result, the Variational Quantum Algorithm (VQA) shows a gain of performance in balanced accuracy with the LDA technique and outperforms baseline classical classifiers.

arXiv:2208.13251•Entropy•Nov 15, 2022•27 citations

Many-body quantum systems provide a mechanism for robust and efficient quantum search

Kostyantyn Kechedzhi, Vadim Smelyanskiy, Lara Faoro +4 more

Bulletin of the American Physical Society•Mar 7, 2019•0 citations

Towards Efficient Function Optimisation with Quantum–Classical Hybrid Search

Mansur Ziatdinov, Fedor Levkovich-Maslyuk, Emmanuel M. Pothos

Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum-classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton-Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.

Entropy•Sep 26, 2026•0 citations

Quantum contextuality with mixed states of 1D symmetry-protected topological order

Leroy Fagan, Akimasa Miyake

Bell theorems of many-body nonlocality and contextuality serve as a benchmark for proving quantum advantage in that a quantum computer outperforms a classical computer for a certain problem. In practice, however, near-term quantum devices do not prepare perfectly pure states but rather mixed states produced from noisy channels. We investigate noisy quantum advantage by considering thermal mixed states of one-dimensional many-body systems with a symmetry-protected topological (SPT) order. In the pure-state (or zero-temperature) case, these states are known to be useful for measurement-based quantum computation, and to outperform classical computers in a many-body contextuality game, provided string order parameters (SOPs) of SPT are sufficiently large. Here, we show that quantum advantage in mixed states is measured by a combination of twisted SOP and symmetry representation expectation values. Using the minimally entangled typical thermal states algorithm, it is demonstrated that quantum advantage persists to a nonzero critical temperature for finite-sized instances of the many-body contextuality game. While this critical temperature goes to zero in the thermodynamic limit, it is relatively robust to system size, suggesting that these states remain useful for demonstrating genuine "quantumness" of noisy hardware in a scalable fashion. Finally, we show that the quantum winning probability is lower bounded by the global fidelity with the 1D cluster state, so that our contextuality game can provide an operational meaning to benchmark the capacity to create long-range order like SPT states in near-term experimental devices.

quant-pharXiv:2603.13626•Mar 17, 2026•0 citations

Hybrid Quantum–Classical Algorithms to Accelerate AI

Bhavya M. Patel

•Jan 1, 2025•0 citations

A scalable quantum-enhanced greedy algorithm for maximum independent set problems

Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi +2 more

We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set (MIS) problem on regular graphs, combining the Quantum Approximate Optimization Algorithm (QAOA) with a minimal degree classical greedy algorithm. The method leverages pre-computed QAOA angles, derived from depth-$p$ QAOA circuits on regular trees, to compute local expectation values and inform sequential greedy decisions that progressively build an independent set. This hybrid approach maintains shallow quantum circuit and avoids instance-specific parameter training, making it well-suited for implementation on current quantum hardware: we have implemented the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes. We perform tensor network simulations to evaluate the performance of the algorithm beyond the reach of current quantum hardware and compare to established classical heuristics. Our results show that even at low depth ($p=4$), the quantum-enhanced greedy method significantly outperforms purely classical greedy baselines as well as more sophisticated approximation algorithms. The modular structure of the algorithm and relatively low quantum resource requirements make it a compelling candidate for scalable, hybrid optimization in the NISQ era and beyond.

quant-pharXiv:2601.21923•Jan 30, 2026•0 citations
Quantum Machine Learning (QML) has not yet demonstrated extensively and clearly its advantages compared to the classical machine learning approach. So far, there are only specific cases where some quantum-inspired techniques have achieved small incremental advantages, and a few experimental cases in hybrid quantum computing are promising, considering a mid-term future (not taking into account the achievements purely associated with optimization using quantum-classical algorithms). The current quantum computers are noisy and have few qubits to test, making it difficult to demonstrate the current and potential quantum advantage of QML methods. This study shows that we can achieve better classical encoding and performance of quantum classifiers by using Linear Discriminant Analysis (LDA) during the data preprocessing step. As a result, the Variational Quantum Algorithm (VQA) shows a gain of performance in balanced accuracy with the LDA technique and outperforms baseline classical classifiers.
Finding the global minimum of a function with many local extrema is well known to be a challenging computational task. We propose a hybrid quantum-classical algorithm for this optimisation problem, based on a combination of Grover quantum search and the classical Newton-Raphson method. The approach is tailored to situations with a large number of false minima. The main idea is to use quantum search to efficiently locate the vicinity of the true optimum, after which a classical algorithm can solve the problem in only a few iterations. We specifically address the nontrivial question of choosing the discretisation of the function domain, which is critical for quantum approaches to optimisation of continuous functions. While we do not expect that this method will always be superior, we identify a paradigmatic case of a function for which we demonstrate that, remarkably, our hybrid method quadratically outperforms a purely classical approach (measuring performance by the number of function/oracle calls). We evaluate key performance metrics of the algorithm in numerical experiments. We furthermore discuss its possible extensions as well as the potential relevance of hybrid approaches in the context of quantum cognition.
Bell theorems of many-body nonlocality and contextuality serve as a benchmark for proving quantum advantage in that a quantum computer outperforms a classical computer for a certain problem. In practice, however, near-term quantum devices do not prepare perfectly pure states but rather mixed states produced from noisy channels. We investigate noisy quantum advantage by considering thermal mixed states of one-dimensional many-body systems with a symmetry-protected topological (SPT) order. In the pure-state (or zero-temperature) case, these states are known to be useful for measurement-based quantum computation, and to outperform classical computers in a many-body contextuality game, provided string order parameters (SOPs) of SPT are sufficiently large. Here, we show that quantum advantage in mixed states is measured by a combination of twisted SOP and symmetry representation expectation values. Using the minimally entangled typical thermal states algorithm, it is demonstrated that quantum advantage persists to a nonzero critical temperature for finite-sized instances of the many-body contextuality game. While this critical temperature goes to zero in the thermodynamic limit, it is relatively robust to system size, suggesting that these states remain useful for demonstrating genuine "quantumness" of noisy hardware in a scalable fashion. Finally, we show that the quantum winning probability is lower bounded by the global fidelity with the 1D cluster state, so that our contextuality game can provide an operational meaning to benchmark the capacity to create long-range order like SPT states in near-term experimental devices.
We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set (MIS) problem on regular graphs, combining the Quantum Approximate Optimization Algorithm (QAOA) with a minimal degree classical greedy algorithm. The method leverages pre-computed QAOA angles, derived from depth-ppp QAOA circuits on regular trees, to compute local expectation values and inform sequential greedy decisions that progressively build an independent set. This hybrid approach maintains shallow quantum circuit and avoids instance-specific parameter training, making it well-suited for implementation on current quantum hardware: we have implemented the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes. We perform tensor network simulations to evaluate the performance of the algorithm beyond the reach of current quantum hardware and compare to established classical heuristics. Our results show that even at low depth (p=4p=4p=4), the quantum-enhanced greedy method significantly outperforms purely classical greedy baselines as well as more sophisticated approximation algorithms. The modular structure of the algorithm and relatively low quantum resource requirements make it a compelling candidate for scalable, hybrid optimization in the NISQ era and beyond.