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:2410.07024 · Physical Review Letters

Role of Coherence for Quantum Computational Advantage

Hugo Thomas, Pierre-Emmanuel Emeriau, Rawad Mezher, Elham Kashefi, Harold Ollivier, Ulysse Chabaud

Published Aug 15, 2025• 10 citations
arXivHTMLPDF

Abstract

Quantifying the resources available to a quantum computer appears to be necessary to separate quantum from classical computation. Among them, entanglement, nonstabilizerness, and coherence are arguably of great significance. We introduce "path coherence" as a measure of the coherent path interferences arising in a quantum computation. Leveraging the sum-over-paths formalism, we obtain a classical algorithm for estimating quantum transition amplitudes, the complexity of which scales with path coherence. As path coherence relates to the hardness of classical estimation of quantum transition amplitudes, it provides a new perspective on the role of coherence in quantum computational advantage. Beyond their fundamental significance, our results have practical applications for simulating large classes of quantum computations with classical computers.

DOI
10.1103/1csn-x1cx

Related papers

Practical Guide to Quantum Computing: Fundamental Quantum Algorithms # 1

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Fundamentals of Quantum Algorithms and explores the computational advantages enabled by quantum information. The focus is on what can be achieved using a single quantum computer, rather than distributed quantum systems. The primary objective of the course is to analyze how quantum computation can outperform classical computation in specific problem classes. In particular, the material examines quantum query algorithms, which provide a structured framework for understanding quantum speedups. Key themes include: The conceptual foundations of quantum computational advantage. The role of superposition, interference, and entanglement in algorithm design. Query complexity and how quantum algorithms reduce the number of required oracle calls compared to classical approaches. Foundational algorithms that demonstrate provable quantum speedups. The central guiding question is: What advantages can a quantum computer potentially offer over a classical computer? Through hands-on experimentation on IBM Q, the work connects theoretical analysis with practical implementation, enabling deeper insight into how quantum resources translate into measurable computational gains.

•Mar 4, 2026•0 citations

A Comparative Study of Classical and Quantum Computing: Concepts, Circuits, and Real-World Applications

K.V. Rama Raoa, N. Srinivasb, K. Rama Krishnaiahc +1 more

Quantum computing leverages quantum-mechanical phenomena such as superposition, entanglement and interference to solve classes of problems that are intractable on classical machines.This paper unifies three complementary perspectives: (i) the central role of complex matrices in modelling quantum states, gates and error-correction protocols; (ii) the pervasive use of trigonometric functions in qubit representation, phase manipulation and the quantum Fourier transform (QFT); and (iii) a systematic comparison of classical and quantum computing paradigms with illustrative circuits and real-world applications.By integrating these dimensions, the study provides a consolidated reference that elucidates the mathematical foundations, circuit constructions, algorithmic advantages and practical challenges that define contemporary quantum information processing.

International Journal of Research Publication and Reviews•Aug 1, 2025•1 citation

Entanglement – nonstabilizerness separation in hybrid quantum circuits

Gerald E. Fux, Emanuele Tirrito, Marcello Dalmonte +1 more

Nonstabilizerness describes the distance of a quantum state to its closest stabilizer state. It is—like entanglement—a necessary resource for a quantum advantage over classical computing. We study nonstabilizerness, quantified by stabilizer entropy, in a hybrid quantum circuit with projective measurements and a controlled injection of non-Clifford resources. We discover a phase transition between a power law and constant scaling of nonstabilizerness with system size controlled by the rate of measurements. The same circuit also exhibits a phase transition in entanglement that appears, however, at a different critical measurement rate. This mechanism shows how, from the viewpoint of a quantum advantage, hybrid circuits can host multiple distinct transitions where not only entanglement, but also other nonlinear properties of the density matrix come into play. Published by the American Physical Society 2024

arXiv:2312.02039•Physical Review Research•Oct 30, 2024•72 citations

Predicting Magic from Very Few Measurements

J. M. Varela, L. L. Keller, A. de Oliveira Junior +3 more

The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of $m$ $n$-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements $m$ and polynomial in the number of qubits $n$. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless $\mathrm{P} = \mathrm{NP}$, no algorithm polynomial in $m$ can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.

quant-pharXiv:2602.18939•PRX Quantum•Feb 24, 2026•11 citations

Quantum Coherence-Based Computational Complexity Analysis

Jincheng Zhang

This paper presents a novel approach to analyzing the computational complexity of quantum algorithms by leveraging the concept of quantum coherence. Traditional methods for assessing quantum complexity often rely on circuit depth, qubit count, or gate complexity, which can be insufficient in capturing the nuances of quantum computation. We introduce a framework that explicitly incorporates the calculation of quantum coherence, recognizing it as a fundamental resource in quantum computation. The core idea is that the precision and duration of quantum coherence directly correlate with the computational effort required. We define a mathematical model that quantifies coherence decay and its impact on algorithm execution time. This model allows us to derive tighter bounds on the complexity of quantum algorithms, particularly those that rely heavily on sustained coherence. Furthermore, we explore the implications of coherence limitations on the feasibility of certain quantum algorithms and suggest potential strategies for mitigating these effects. This work contributes a new perspective on quantum complexity analysis, providing a more accurate and potentially more scalable method for evaluating quantum algorithms.

•Sep 3, 2026•0 citations

What is Quantum Parallelism, Anyhow?

Stefano Markidis

Central to the power of quantum computing is the concept of quantum parallelism: quantum systems can explore and process multiple computational paths simultaneously. In this paper, we discuss the elusive nature of quantum parallelism, drawing parallels with classical parallel computing models to elucidate its fundamental characteristics and implications for algorithmic performance. We begin by defining quantum parallelism as arising from the superposition of quantum states, allowing for the exploration of multiple computational paths in parallel. To quantify and visualize quantum parallelism, we introduce the concept of quantum dataflow diagrams, which provide a graphical representation of quantum algorithms and their parallel execution paths. We demonstrate how quantum parallelism can be measured and assessed by analyzing quantum algorithms such as the Quantum Fourier Transform (QFT) and Amplitude Amplification (AA) iterations using quantum dataflow diagrams. Furthermore, we examine the interplay between quantum parallelism and classical parallelism laws, including Amdahl's and Gustafson's laws. While these laws were originally formulated for classical parallel computing systems, we reconsider their applicability in the quantum computing domain. We argue that while classical parallelism laws offer valuable insights, their direct application to quantum computing is limited due to the unique characteristics of quantum parallelism, including the role of destructive interference and the inherent limitations of classical-quantum I/O. Our analysis highlights the need for an increased understanding of quantum parallelism and its implications for algorithm design and performance.

arXiv:2405.07222•ISC High Performance (ISC)•May 1, 2024•27 citations
Quantifying the resources available to a quantum computer appears to be necessary to separate quantum from classical computation. Among them, entanglement, nonstabilizerness, and coherence are arguably of great significance. We introduce "path coherence" as a measure of the coherent path interferences arising in a quantum computation. Leveraging the sum-over-paths formalism, we obtain a classical algorithm for estimating quantum transition amplitudes, the complexity of which scales with path coherence. As path coherence relates to the hardness of classical estimation of quantum transition amplitudes, it provides a new perspective on the role of coherence in quantum computational advantage. Beyond their fundamental significance, our results have practical applications for simulating large classes of quantum computations with classical computers.
Abstract This guide is based on the IBM Quantum course Fundamentals of Quantum Algorithms and explores the computational advantages enabled by quantum information. The focus is on what can be achieved using a single quantum computer, rather than distributed quantum systems. The primary objective of the course is to analyze how quantum computation can outperform classical computation in specific problem classes. In particular, the material examines quantum query algorithms, which provide a structured framework for understanding quantum speedups. Key themes include: The conceptual foundations of quantum computational advantage. The role of superposition, interference, and entanglement in algorithm design. Query complexity and how quantum algorithms reduce the number of required oracle calls compared to classical approaches. Foundational algorithms that demonstrate provable quantum speedups. The central guiding question is: What advantages can a quantum computer potentially offer over a classical computer? Through hands-on experimentation on IBM Q, the work connects theoretical analysis with practical implementation, enabling deeper insight into how quantum resources translate into measurable computational gains.
Quantum computing leverages quantum-mechanical phenomena such as superposition, entanglement and interference to solve classes of problems that are intractable on classical machines.This paper unifies three complementary perspectives: (i) the central role of complex matrices in modelling quantum states, gates and error-correction protocols; (ii) the pervasive use of trigonometric functions in qubit representation, phase manipulation and the quantum Fourier transform (QFT); and (iii) a systematic comparison of classical and quantum computing paradigms with illustrative circuits and real-world applications.By integrating these dimensions, the study provides a consolidated reference that elucidates the mathematical foundations, circuit constructions, algorithmic advantages and practical challenges that define contemporary quantum information processing.
Nonstabilizerness describes the distance of a quantum state to its closest stabilizer state. It is—like entanglement—a necessary resource for a quantum advantage over classical computing. We study nonstabilizerness, quantified by stabilizer entropy, in a hybrid quantum circuit with projective measurements and a controlled injection of non-Clifford resources. We discover a phase transition between a power law and constant scaling of nonstabilizerness with system size controlled by the rate of measurements. The same circuit also exhibits a phase transition in entanglement that appears, however, at a different critical measurement rate. This mechanism shows how, from the viewpoint of a quantum advantage, hybrid circuits can host multiple distinct transitions where not only entanglement, but also other nonlinear properties of the density matrix come into play. Published by the American Physical Society 2024
The nonstabilizerness of quantum states is a necessary resource for universal quantum computation, yet its characterization is notoriously demanding. Quantifying nonstabilizerness typically requires an exponential number of measurements and a doubly exponential classical post-processing cost to evaluate its standard monotones. In this work, we show that nonstabilizerness is, to a large extent, in the eyes of the beholder: it can be witnessed and quantified using any set of mmm nnn-qubit Pauli measurements, provided the set contains anti-commuting pairs. We introduce a general framework that projects the stabilizer polytope onto the subspace defined by these observables and provide an algorithm that estimates magic from Pauli expectation values with runtime exponential in the number of measurements mmm and polynomial in the number of qubits nnn. By relating the problem to a stabilizer-restricted variant of the quantum marginal problem, we also prove that deciding membership in the corresponding reduced stabilizer polytope is NP-hard. In particular, unless P=NP\mathrm{P} = \mathrm{NP}P=NP, no algorithm polynomial in mmm can solve the problem in full generality, thus establishing fundamental complexity-theoretic limitations. Finally, we employ our framework to compute nonstabilizerness in different Hamiltonian ground states, demonstrating the practical performance of our method in regimes beyond the reach of existing techniques.
This paper presents a novel approach to analyzing the computational complexity of quantum algorithms by leveraging the concept of quantum coherence. Traditional methods for assessing quantum complexity often rely on circuit depth, qubit count, or gate complexity, which can be insufficient in capturing the nuances of quantum computation. We introduce a framework that explicitly incorporates the calculation of quantum coherence, recognizing it as a fundamental resource in quantum computation. The core idea is that the precision and duration of quantum coherence directly correlate with the computational effort required. We define a mathematical model that quantifies coherence decay and its impact on algorithm execution time. This model allows us to derive tighter bounds on the complexity of quantum algorithms, particularly those that rely heavily on sustained coherence. Furthermore, we explore the implications of coherence limitations on the feasibility of certain quantum algorithms and suggest potential strategies for mitigating these effects. This work contributes a new perspective on quantum complexity analysis, providing a more accurate and potentially more scalable method for evaluating quantum algorithms.
Central to the power of quantum computing is the concept of quantum parallelism: quantum systems can explore and process multiple computational paths simultaneously. In this paper, we discuss the elusive nature of quantum parallelism, drawing parallels with classical parallel computing models to elucidate its fundamental characteristics and implications for algorithmic performance. We begin by defining quantum parallelism as arising from the superposition of quantum states, allowing for the exploration of multiple computational paths in parallel. To quantify and visualize quantum parallelism, we introduce the concept of quantum dataflow diagrams, which provide a graphical representation of quantum algorithms and their parallel execution paths. We demonstrate how quantum parallelism can be measured and assessed by analyzing quantum algorithms such as the Quantum Fourier Transform (QFT) and Amplitude Amplification (AA) iterations using quantum dataflow diagrams. Furthermore, we examine the interplay between quantum parallelism and classical parallelism laws, including Amdahl's and Gustafson's laws. While these laws were originally formulated for classical parallel computing systems, we reconsider their applicability in the quantum computing domain. We argue that while classical parallelism laws offer valuable insights, their direct application to quantum computing is limited due to the unique characteristics of quantum parallelism, including the role of destructive interference and the inherent limitations of classical-quantum I/O. Our analysis highlights the need for an increased understanding of quantum parallelism and its implications for algorithm design and performance.