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
Koh Enshan, Dax

Koh Enshan, Dax

Joined August 20, 2026

Karma 0

Overview
Last submissions
Datasets
Workspaces
Papers
Last comments
Last topics
Organizations

Training Variational Quantum Algorithms Is NP-Hard, Even Locally

Dax Enshan Koh, Triscia Mundo, Iosif Sakos +1 more

Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be $\mathsf{NP}$-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly $\mathsf{NP}$-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within $\ell_p$-distance strictly less than $π/2$ of some local minimizer, for every $p\geq 1$. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly $\mathsf{NP}$-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.

quant-pharXiv:2610.05128•Oct 6, 2026•0 citations

Verification Complexity and Extension of Classical Shadows

Georgios Karaiskos, Asad Raza, Dorian Rudolph +2 more

Classical shadows are an influential framework for compressing copies of a given quantum state $ρ$ into classical data $S$, enabling many properties of $ρ$ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given $S$, when can one efficiently verify that $S$ came from a genuine $n$-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given $S$ that allows one to capture 2-local properties of $ρ$, can one fake or spoof a shadow $S'$ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all $n$-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-$Σ_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$Σ_2$ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals $S$ of a quantum state $ρ$, estimating the 3-local marginals of $ρ$ is intractable unless QCMA $\subseteq$ BPP, even if the state $ρ$ is the unique state consistent with $S$.

quant-pharXiv:2609.40107•Oct 1, 2026•0 citations

Practical Error Suppression and Mitigation for Reliable Quantum Computing

Han-Ze Li, Mengjie Yang, Xianquan Yan +3 more

Quantum computing is entering a transitional regime between noisy intermediate-scale quantum (NISQ) processing and early fault-tolerant quantum computation (FTQC), in which increasingly capable hardware is beginning to support repeated syndrome measurements, partial error correction, and logical-qubit operations, while residual physical and logical errors remain non-negligible. In this regime, error suppression, error mitigation, and quantum error correction are increasingly better viewed as complementary layers of a unified error-reduction strategy rather than as separate approaches, with each acting at a different stage of the quantum computation to improve simulation reliability. Thus, in this review, we provide a practical and forward-looking overview of the principal hardware error sources and the corresponding error suppression and mitigation methods for reducing their impact across the current NISQ-FTQC transition. We discuss hardware-aware circuit design, coherent-error suppression, readout mitigation, noise extrapolation, classical inference, and software-supported workflows, with particular emphasis on their implementation on actual quantum processors. We further examine how error mitigation techniques can be adapted to encoded and logical-qubit settings so that they can operate alongside quantum error correction to suppress residual logical errors and improve the accuracy of computation in the early fault-tolerant regime.

quant-pharXiv:2608.20453•Aug 24, 2026•4 citations

Real Classical Shadows with Noise

Atharva Hingane, Dax Enshan Koh

The real classical shadows protocol of West et al. replaces the unitary (Clifford) ensemble of the Huang--Kueng--Preskill scheme by the orthogonal (real Clifford) ensemble, and for symmetric observables achieves strictly smaller estimator variances: a factor approaching two for global evolution and an exponential factor $(3/2)^k$ for $k$-local real Pauli observables. Real hardware, however, never implements the ideal evolution. Building on the noisy classical shadows framework of Koh and Grewal, we give a complete theory of the real classical shadows protocol in the presence of a known completely positive trace-preserving noise channel acting after the orthogonal evolution. We derive the noisy global and local orthogonal shadow channels from first principles using the Weingarten calculus of the orthogonal group, prove that each is a depolarizing channel acting on the symmetric (respectively locally symmetric) component of its input, and derive from it the exact single-shot variance in closed form, together with the associated shadow seminorm, two-sided bounds on it, and the resulting sample-complexity guarantees. We prove that the noiseless sample-complexity advantages survive intact under noise. Because the variances are exact rather than bounded, the ratio is controlled by a single dimensionless parameter, which gives a closed-form criterion for when the factor of two is attainable: both the second-moment and the variance ratio reach it exactly when the observable's norm profile grows, and the noise enters that limit only through a factor lying within $2/(d+2)$ of two, so the advantage is uniform in the noise. For rank-one targets it is provably unattainable, saturating strictly below two. The local real-Pauli advantage remains $(3/2)^k$. We treat complex measurement bases through a reality parameter and a transposed-noise scalar, recovering unitary shadows in the appropriate limit.

quant-pharXiv:2608.18935•Aug 20, 2026•1 citation

CoQui: A Coordinate-Conditioned Quantum Implicit Generative Adversarial Network for End-to-End Image Generation

Xue Yang, Rigui Zhou, ShiZheng Jia +7 more

Quantum generative adversarial networks (QGANs) have attracted increasing attention for image generation using parameterized quantum circuits. Existing amplitude-based approaches face two key limitations: pixel locations are typically encoded by computational-basis indices or address qubits, causing quantum resources to grow with image resolution; meanwhile, jointly decoding many pixels from normalized quantum states introduces probability competition among pixels and limits precise pixel-wise control. To address these issues, we reformulate quantum image generation as coordinate-conditioned implicit function learning. Our method takes spatial coordinates and latent variables as inputs, uses a classical embedding network to generate input-dependent circuit parameters, and evaluates a variational quantum circuit at each coordinate. Pixel intensities are directly obtained from the expectation value of a dedicated color qubit, and a complete image is generated by querying all spatial coordinates. This design decouples image resolution from address-qubit requirements and avoids shared probability-normalization constraints across pixels. We further design a specialized variational quantum circuit to provide structural inductive bias for coordinate-conditioned generation. Simulated experiments on two benchmark datasets show that our method outperforms FRQI-based generation and PQWGAN in visual and quantitative quality while using fewer qubits, and also achieves better generation quality than the corresponding classical baseline.

quant-pharXiv:2608.11884•Aug 13, 2026•0 citations

Entanglement in the Quantum Volunteer's Dilemma

Noah Dane Hebdon, Dax Enshan Koh

A well-known model in game theory, the Volunteer's Dilemma describes a group of $n$ players who decide whether to volunteer for a collective benefit at a personal cost, or to abstain and risk forfeiting the benefit altogether. A quantum version of this dilemma, developed within the Eisert-Wilkens-Lewenstein framework, allows each player to manipulate one qubit of a shared entangled state, leading to symmetric Nash equilibria with higher expected payoffs than in the classical game. Existing analyses, however, assume maximal entanglement, which is experimentally demanding for hardware-constrained quantum systems. Within the same framework, we introduce a generalized Quantum Volunteer's Dilemma with a tunable entanglement parameter $γ$ and study the extent to which equilibrium behavior depends on the level of entanglement. We derive explicit conditions relating $γ$, the number of players, and the players' strategies under which symmetric Nash equilibria exist, focusing on two canonical strategy profiles: one for $2\leq n\leq 9$, and one for even $n$. We find that maximal entanglement is not required to sustain symmetric equilibria. Instead, equilibrium behavior persists above a threshold value, which we compute analytically in both cases. We also demonstrate that the threshold value directly depends on system size.

quant-pharXiv:2606.08227•Physical Review A•Jun 9, 2026•0 citations
Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be NP\mathsf{NP}NP-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly NP\mathsf{NP}NP-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within ℓp\ell_pℓp​-distance strictly less than π/2π/2π/2 of some local minimizer, for every p≥1p\geq 1p≥1. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly NP\mathsf{NP}NP-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.
Classical shadows are an influential framework for compressing copies of a given quantum state ρρρ into classical data SSS, enabling many properties of ρρρ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given SSS, when can one efficiently verify that SSS came from a genuine nnn-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given SSS that allows one to capture 2-local properties of ρρρ, can one fake or spoof a shadow S′S'S′ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all nnn-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-Σ2Σ_2Σ2​ ⊆\subseteq⊆ PPP\mathrm{P}^{\mathrm{PP}}PPP, where qc-Σ2Σ_2Σ2​ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals SSS of a quantum state ρρρ, estimating the 3-local marginals of ρρρ is intractable unless QCMA ⊆\subseteq⊆ BPP, even if the state ρρρ is the unique state consistent with SSS.
Quantum computing is entering a transitional regime between noisy intermediate-scale quantum (NISQ) processing and early fault-tolerant quantum computation (FTQC), in which increasingly capable hardware is beginning to support repeated syndrome measurements, partial error correction, and logical-qubit operations, while residual physical and logical errors remain non-negligible. In this regime, error suppression, error mitigation, and quantum error correction are increasingly better viewed as complementary layers of a unified error-reduction strategy rather than as separate approaches, with each acting at a different stage of the quantum computation to improve simulation reliability. Thus, in this review, we provide a practical and forward-looking overview of the principal hardware error sources and the corresponding error suppression and mitigation methods for reducing their impact across the current NISQ-FTQC transition. We discuss hardware-aware circuit design, coherent-error suppression, readout mitigation, noise extrapolation, classical inference, and software-supported workflows, with particular emphasis on their implementation on actual quantum processors. We further examine how error mitigation techniques can be adapted to encoded and logical-qubit settings so that they can operate alongside quantum error correction to suppress residual logical errors and improve the accuracy of computation in the early fault-tolerant regime.
The real classical shadows protocol of West et al. replaces the unitary (Clifford) ensemble of the Huang--Kueng--Preskill scheme by the orthogonal (real Clifford) ensemble, and for symmetric observables achieves strictly smaller estimator variances: a factor approaching two for global evolution and an exponential factor (3/2)k(3/2)^k(3/2)k for kkk-local real Pauli observables. Real hardware, however, never implements the ideal evolution. Building on the noisy classical shadows framework of Koh and Grewal, we give a complete theory of the real classical shadows protocol in the presence of a known completely positive trace-preserving noise channel acting after the orthogonal evolution. We derive the noisy global and local orthogonal shadow channels from first principles using the Weingarten calculus of the orthogonal group, prove that each is a depolarizing channel acting on the symmetric (respectively locally symmetric) component of its input, and derive from it the exact single-shot variance in closed form, together with the associated shadow seminorm, two-sided bounds on it, and the resulting sample-complexity guarantees. We prove that the noiseless sample-complexity advantages survive intact under noise. Because the variances are exact rather than bounded, the ratio is controlled by a single dimensionless parameter, which gives a closed-form criterion for when the factor of two is attainable: both the second-moment and the variance ratio reach it exactly when the observable's norm profile grows, and the noise enters that limit only through a factor lying within 2/(d+2)2/(d+2)2/(d+2) of two, so the advantage is uniform in the noise. For rank-one targets it is provably unattainable, saturating strictly below two. The local real-Pauli advantage remains (3/2)k(3/2)^k(3/2)k. We treat complex measurement bases through a reality parameter and a transposed-noise scalar, recovering unitary shadows in the appropriate limit.
Quantum generative adversarial networks (QGANs) have attracted increasing attention for image generation using parameterized quantum circuits. Existing amplitude-based approaches face two key limitations: pixel locations are typically encoded by computational-basis indices or address qubits, causing quantum resources to grow with image resolution; meanwhile, jointly decoding many pixels from normalized quantum states introduces probability competition among pixels and limits precise pixel-wise control. To address these issues, we reformulate quantum image generation as coordinate-conditioned implicit function learning. Our method takes spatial coordinates and latent variables as inputs, uses a classical embedding network to generate input-dependent circuit parameters, and evaluates a variational quantum circuit at each coordinate. Pixel intensities are directly obtained from the expectation value of a dedicated color qubit, and a complete image is generated by querying all spatial coordinates. This design decouples image resolution from address-qubit requirements and avoids shared probability-normalization constraints across pixels. We further design a specialized variational quantum circuit to provide structural inductive bias for coordinate-conditioned generation. Simulated experiments on two benchmark datasets show that our method outperforms FRQI-based generation and PQWGAN in visual and quantitative quality while using fewer qubits, and also achieves better generation quality than the corresponding classical baseline.
A well-known model in game theory, the Volunteer's Dilemma describes a group of nnn players who decide whether to volunteer for a collective benefit at a personal cost, or to abstain and risk forfeiting the benefit altogether. A quantum version of this dilemma, developed within the Eisert-Wilkens-Lewenstein framework, allows each player to manipulate one qubit of a shared entangled state, leading to symmetric Nash equilibria with higher expected payoffs than in the classical game. Existing analyses, however, assume maximal entanglement, which is experimentally demanding for hardware-constrained quantum systems. Within the same framework, we introduce a generalized Quantum Volunteer's Dilemma with a tunable entanglement parameter γγγ and study the extent to which equilibrium behavior depends on the level of entanglement. We derive explicit conditions relating γγγ, the number of players, and the players' strategies under which symmetric Nash equilibria exist, focusing on two canonical strategy profiles: one for 2≤n≤92\leq n\leq 92≤n≤9, and one for even nnn. We find that maximal entanglement is not required to sustain symmetric equilibria. Instead, equilibrium behavior persists above a threshold value, which we compute analytically in both cases. We also demonstrate that the threshold value directly depends on system size.