Quantum Machine Learning

Quantum machine learning (QML) aims to accelerate machine learning tasks by exploiting quantum computation. Previous work studied a QML algorithm for selecting sparse subnetworks from large shallow neural networks. Instead of directly solving an optimization problem over a large-scale network, this algorithm constructs a sparse subnetwork by sampling hidden nodes from an optimized probability distribution defined using the ridgelet transform. The quantum algorithm performs this sampling in time $O(D)$ in the data dimension $D$, whereas a naive classical implementation relies on handling exponentially many candidate nodes and hence takes $\exp[O(D)]$ time. In this work, we construct and analyze a quantum-inspired fully classical algorithm for the same sampling task. We show that our algorithm runs in time $O(\operatorname{poly}(D))$, thereby removing the exponential dependence on $D$ from the previous classical approach. Numerical simulations show that the proposed sampler achieves empirical risk comparable to exact sampling from the optimized distribution and substantially lower than sampling from the non-optimized uniform distribution, while also exhibiting exponentially improved runtime scaling compared with the conventional classical implementation. These successful dequantization results show that sparse subnetwork selection via optimized sampling can be achieved classically with polynomial data-dimension scaling on conventional computers without quantum hardware, providing an alternative to the existing quantum algorithm.

Computing the partition function $\mathcal{Z} = \mathrm{tr}(e^{-\beta H})$ of a quantum spin Hamiltonian $H$ on $n$ sites is a fundamental problem in statistical physics and quantum chemistry. However exact evaluation requires $O(8^n)$ time and $O(4^n)$ memory making it intractable for all but the smallest systems. We propose an unbiased stochastic estimator of $\mathcal{Z}$, and more generally of $\mathrm{tr}(f(H))$ for any function $f$ admitting a convergent power series over exponentially large, implicitly defined operators using only local random walks, avoiding both matrix materialization and matrix-vector products. Our approach combines Graph Random Features with the Hutchinson's stochastic trace estimator, and exploits the algebraic structure of quantum spin Hamiltonians to reduce the per-step computational cost to $O(n + d)$, where $d$ is the mean degree of the spin coupling graph, independent of the Hilbert space dimension $N = 2^n$. We validate the estimator empirically against exact matrix exponentiation for small system sizes, and demonstrate its applicability to system sizes where exact methods are infeasible.

Choosing where to place entangling gates is a central design choice in quantum machine learning circuits, yet entanglers are still typically chosen from fixed templates or by expensive search procedures requiring training or pairwise kernel evaluations. We propose the \emph{HSD-Lipschitz principle}, a training-free geometric criterion built on a simple intuition: a useful entangler should keep encoded states stable across the dataset while separating different classes. We formalise this through a two-sided bound on local light-cone subsystems. Under a light-cone locality assumption, dataset-level gradient variance is upper-bounded by reduced-state spread; under random initialisation, the expected between-class gradient signal is lower-bounded by class-conditional reduced-state distance. The resulting algorithm, HSD-greedy, adaptively grows an entanglement structure using only single-state reduced moments, estimable via classical shadows, and avoids the $\mathcal{O}(N^2)$ pairwise kernel evaluations of kernel-target alignment proxies. Empirically, both bounds hold without violation across $110$ topologies and $440$ parameter rows, and extend to $180$ additional configurations. HSD-greedy attains the strongest average AUC among training-free entangler selectors on synthetic and real-world benchmarks, at roughly $60\times$ lower selection cost than the strongest baseline in 13-qubit simulation. End-to-end execution on a 20-qubit IBM Eagle subchain substantially outperforms a fixed 19-CNOT Linear chain and matches or exceeds a matched-budget Random baseline while using far fewer two-qubit gates than the Linear chain.

The mechanism governing the training dynamics of Quantum Neural Networks (QNNs) remains under-explored. In classical Deep Neural Networks (DNNs), training is known dominated by "Spectral Bias,'' i.e. prioritizing learning low-frequency while struggling with high-frequency. QNNs exhibit similar spectral limitations when the target function possesses flat spectral amplitudes. However, in this work, considering target problems with different spectral amplitudes, we theoretically and empirically identify a distinct mechanism in QNNs, which we term *Spectral Amplitude Priority*. By analyzing the frequency-domain gradients and residual dynamics via the Quantum Neural Tangent Kernel (QNTK), we prove that QNN training is governed primarily by the magnitude of spectral components rather than their frequency indices. Consequently, QNNs can efficiently capture high-frequency functions—provided they have significant amplitude—thereby overcoming the inherent limitations of their classical counterparts. We validate this principle on both synthetic high-frequency functions and quantum-advantage tasks. These results show that QNNs notably outperform DNNs in high-frequency tasks, offering an explanation for QNNs' superior expressivity.

Programmable photonic circuits are a natural platform for physical learning, where the learned computation is performed by the hardware itself rather than by a digital model. We propose a physical learning algorithm and architecture for continuous-variable quantum systems where a photonic circuit is configured in situ to invert an unknown lossless Gaussian quantum operation. Our contributions are threefold. (i) Theory: we prove that generic $S \in \mathrm{Sp}(2 N, \mathbb{R})$ admits a triangular decomposition into two-mode and single-mode symplectic gates. (ii) Architecture: we introduce the symplectic Reck mesh, a triangular array of two-mode symplectic gates that physically realizes this factorization, generalizing the unitary Reck mesh widely used in optical neural networks. (iii) Physical learning: when placed after an unknown Gaussian unitary, the mesh is trained in situ by nulling local response blocks one at a time using simple optical probes and measurements. We identify a measure that predicts when training becomes hard and numerically demonstrate finite-shot training and robustness to gate errors. Our work extends self-configuring optical networks from unitary to symplectic transformations, bringing physical learning to continuous-variable quantum photonic hardware.

Encoding classical data into quantum states is a central bottleneck in quantum machine learning: many widely used encodings are circuit-inefficient, requiring deep circuits and substantial quantum resources, which limits scalability on quantum hardware. In this work, we propose TNQE, a circuit-efficient quantum data encoding framework built on structured unitary tensor network (TN) representations. TNQE first represents each classical input via a TN decomposition and then compiles the resulting tensor cores into an encoding circuit through two complementary core-to-circuit strategies. To make this compilation trainable while respecting the unitary nature of quantum operations, we introduce a unitary-aware constraint that parameterizes TN cores as learnable block unitaries, enabling them to be directly optimized and directly encoded as quantum operators. The proposed TNQE framework enables explicit control over circuit depth and qubit resources, allowing the construction of shallow, resource-efficient circuits. Across a range of benchmarks, TNQE achieves encoding circuits as shallow as $0.04\times$ the depth of amplitude encoding, while naturally scaling to high-resolution images ($256 \times 256$) and demonstrating practical feasibility on real quantum hardware.

This paper argues that the NeurIPS community should prioritize AI-for-Quantum (AI4Q) over Quantum Machine Learning (QML) on classical data, and should review the two directions by different evidentiary standards. We argue that QML on classical data has not earned high priority because its leading advantage claims rely on strong input assumptions, face trainability and noise barriers, and still lacks persuasive wall-clock wins on the standard benchmarks. By contrast, AI4Q has already produced concrete gains in decoding, compilation, neural-state representation, tomography and readout, and error mitigation. We make the evidentiary standard explicit through falsification criteria and concrete review-process recommendations.

Stochastic reconfiguration (SR) is the standard optimizer for neural quantum states (NQS), but modern NQS often have far more parameters than Monte Carlo samples. We show that in this regime the diagonal shift is more than a numerical stabilizer. It acts as a statistical filter for finite-sample generalization. At a fixed wave function, SR is ridge regression from tangent features to the centered local energy. Its residual is the expressivity gap, the part of imaginary-time evolution outside the current tangent space. This gap is orthogonal to the tangent space in population, but finite batches make it act as noise that SR can overfit. The shift therefore balances shrinkage of useful update directions against variance from fitting sampled residuals. Exact $4\times4$ $J_1$-$J_2$ experiments separate two effects of overparameterization. Larger tangent spaces help when they reduce the expressivity gap, but they can hurt when they overfit a fixed gap. In a $100$-site transverse-field Ising family trained with a foundation NQS, validation risk is U-shaped in the shift while variance decreases, matching the noisy-ridge model. This view leads to multi-shift SR (MS-SR), which averages independent ridge solves at data-adaptive shifts to form a richer, lower-variance spectral filter. MS-SR lowers validation risk and stays closer to the ideal tangent-space imaginary-time update compared to other competitive NQS optimizers.

Quantum state tomography of pure non-Gaussian states is fundamentally limited by scarce and noisy data due to measurement-induced collapse and experimental drift. We introduce a novel reconstruction framework that parameterizes the wavefunction directly via an overparameterized neural network, trained using rank-1 factored gradient descent. We rigorously prove that this formulation's loss landscape is devoid of spurious local minima and strict saddles, guaranteeing all critical points are global minima. By utilizing the max-sliced Wasserstein-1 distance, our loss perfectly maps to the structure of homodyne measurements, structurally preventing gradient vanishing in low-shot regimes. On noisy two-mode cat states, our method achieves continuous fidelity improvements, successfully bypassing the noise-floor plateaus that limit standard iterative maximum-likelihood estimation.

Score-based variational inference (VI) provides an alternative to Kullback--Leibler (KL)-based VI by minimizing the Fisher divergence between the variational distribution and the target. Existing eigenvalue-based score-VI methods face two high-dimensional obstacles: exponential parameter growth and instability under degenerate or nearly degenerate low-energy eigenspaces. We propose QuanVI, a scalable quantum-inspired algorithm that combines a mixed-state density-operator formulation with an MPO-motivated quantum tensor network (QTN) parameterization. The former represents degenerate low-energy eigenspaces by their maximally mixed state, avoiding arbitrary eigenvector selection; the latter realizes a compact density operator without explicitly constructing exponentially large matrices. Experiments and ablations show that QuanVI preserves low-dimensional accuracy while scaling to high-dimensional synthetic and Bayesian posterior-approximation benchmarks, including challenging non-Gaussian targets.

Recent advances in online learning have achieved an $O(n/\Delta_{[2]})$ query complexity in quantum $n$-arm multi-armed bandits (MABs) for best-arm identification, which represents a quadratic speedup over their classical counterparts. Here and throughout, $\Delta_{[2]}$ is the gap between the mean of the best and second-best arms. However, the implementations of these algorithms remain on a small scale due to various aspects of quantum hardware restrictions. One of the most significant restrictions is \emph{memory decoherence}, in which the qubits quickly lose information after a short period of time. Memory decoherence can occur at \emph{intra-circuit} and \emph{inter-circuit} levels. Intra-circuit decoherence happens often in near-term quantum computers, where the noise becomes overwhelming when the circuit is deep. On the other hand, inter-circuit decoherence captures future quantum machines, where a quantum memory is promising, but objects stored in the memory for too long can still become decoherent. In this paper, we present a comprehensive treatment of both memory decoherence problems. For inter-circuit decoherence, we derive a framework based on streaming bandits, and we obtain an algorithm that finds the best arm with high constant probability using $O(n/\Delta_{[2]})$ queries and an $O(\log{n})$ decoherence window. This is the first quantum algorithm for MABs that achieves an $o(n)$ decoherence window, which represents an exponential improvement. For intra-circuit decoherence, we observe that only $O(1)$-depth circuits can be used to avoid significant decoherence. Therefore, we devise various hardware optimizations and a destructive SWAP test subroutine to speed up the empirical performance. On the IBM Q System One machine with 127 qubits, our implementation scales the quantum MABs to over $1000$ arms, and our algorithms consistently achieve significant efficiency improvements over classical bandit algorithms in both physical experiments and computer simulations.

We present a method of quantum composite hypothesis testing with small error, which enables us to establish quantum lower bounds in nonparametric statistics and high-dimensional functional estimation. This is achieved by introducing trigonometric polynomials into the quantum polynomial method, thereby generalizing the quantum phase-estimation lower bound of Mande and de Wolf (ESA 2023). As applications, we settle the quantum complexities of several problems in property testing and functional estimation with small error: - For $\ell_2$-closeness testing, we show that the approach of Luo et al. (*IEEE Trans. Inf. Theory* 2024) is optimal. - For Tsallis entropy estimation, where $q=2$ corresponds to the Gini impurity, we show that the approaches of Buhrman et al. (*Phys. Rev. Lett.* 2001) and Ekert et al. (*Phys. Rev. Lett.* 2002) are optimal for integer $q \geq 2$, and that the approach of Chen et al. (ICALP 2026) is near-optimal for real $q \geq 1.5$. - For pure-state Uhlmann fidelity and trace distance estimation, we show that the approach of Wang (*IEEE Trans. Inf. Theory* 2024) is optimal.

Best arm identification, also known as pure exploration, is a fundamental problem in the multi-armed bandit (MAB) model. Recent quantum algorithms achieve $O(n/\Delta_{[2]})$ query complexity for identifying the best arm with high constant probability, but all of them require $\Omega(\log(1/\Delta_{[2]}))$ or $\Omega(\log n)$ adaptive rounds. Motivated by the practical cost of adaptivity on near-term quantum hardware, where each round incurs substantial overhead from state re-preparation and classical--quantum communication, we study quantum best arm identification with no or very limited adaptivity. On the lower bound side, we prove that any non-adaptive quantum algorithm must make $\Omega(n\log n)$ queries when $\Delta_{[2]}=O(1)$, establishing a separation between adaptive and non-adaptive algorithms. To complement this lower bound, we present an algorithm that identifies the best arm with high constant probability using $O(n/\Delta_{[2]})$ queries and only $\log^*(n)+1$ adaptive rounds. En route to the lower bound, we show that the instances and techniques used to prove adaptivity lower bounds for classical bandits, such as those of Agarwal et al. [COLT'17], do not extend to the quantum setting. As such, we employ the polynomial method to prove our adaptivity lower bounds. To the best of our knowledge, this represents the first application of the polynomial method in this context, which may be of independent interest.

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a weighted sum of $N$ kernel values to additive precision $\varepsilon$, where $\alpha$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $\mathcal{O}(N\lVert\alpha\rVert_2^2/\varepsilon^2)$. In this work, we combine two independent improvements: estimating the kernel values via quantum amplitude estimation and collecting the sum under a single observable. We show that the improved approach achieves a query complexity of $\mathcal{O}(\lVert\alpha\rVert_1/\varepsilon)$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVert\alpha\rVert_1$ and $\varepsilon$. We prove a matching lower bound of $\Omega(\lVert\alpha\rVert_1/\varepsilon)$, establishing query-optimality. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. We identify a different strategy based on importance sampling, which yields a lower total gate count. We thus provide both a query-optimal algorithm and a practically-optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

In quantum systems, physical quantities of interest can often be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to high energy or condensed matter physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widely used in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call by around an order of magnitude, while retaining accurate results.

Instantaneous Quantum Polynomial Quantum Circuit Born Machines (IQP-QCBMs) have been proposed as quantum generative models that combine a classically tractable training objective—based on the maximum mean discrepancy (MMD)—with a potential quantum advantage motivated by sampling-complexity arguments. While recent works have explored this model across various application domains, fundamental questions remain: does the model suffer from exponentially vanishing loss gradients, known as the barren plateau problem—a pervasive obstacle in quantum machine learning—and how do regimes of trainability relate to regimes of possible quantum advantage? Here, we address both questions analytically. To study trainability, we derive closed-form expressions for the variances of the partial derivatives of the MMD loss function and establish general upper and lower bounds. We explicitly characterize how trainability depends on the generator set and the spectrum of the chosen kernel, identifying regimes in which low-weight kernels avoid exponential gradient suppression under structured topologies. Regarding potential quantum advantage, we reformulate the anti-concentration property in terms of the same generator-set quantities that govern trainability, enabling a unified analysis. We show that sparse IQP architectures can produce classically intractable output distributions while simultaneously remaining trainable, at least at lower-weight frequencies. Our analytical results corroborate the numerical observations of prior work and provides principled guidelines for designing scalable IQP-QCBM architectures.

Finite-shot quantum tomography often leaves a posterior over many density matrices compatible with the same measurement record, but fast reconstruction methods collapse this uncertainty to a single state. We frame this setting as amortized posterior sampling and introduce BuresTomFlow, a measurement-conditioned Flow Matching sampler for full-rank density matrices. The method transports base density matrices along Bures-Wasserstein paths on the positive matrix cone, projects the path back to the trace-one state space, and trains the velocity field with a Bures-aligned tangent loss. Thus the sampler is trained in the same fidelity-based geometry used to judge posterior quality. We evaluate BuresTomFlow in dense four-qubit simulations with count, shadow, and mixed measurement records. Against Cholesky, log-density, and generic Riemannian Flow Matching controls at comparable learned-sampler runtime, BuresTomFlow improves Bures distance, credible-ball coverage, and held-out observable prediction. In the main comparison across multiple seeds, mean Bures distance decreases from $0.618$ for the Cholesky baseline to $0.367$ for BuresTomFlow, and mean coverage error decreases from $0.203$ to $0.100$. These results show that the value of Bures geometry is not merely enforcing physical states, but producing calibrated posterior uncertainty when finite-record tomography cannot be reduced to one reconstruction.

It remains unclear whether quantum machine learning (QML) truly holds an advantage when tackling practical and meaningful tasks. In exploring this question, the importance of classical data encoding, often overlooked, becomes increasingly evident. Amplitude encoding, which can embed $2^n$ classical data into $n$ qubits, is widely used due to its apparent efficiency. However, its potential limitations for QML have yet to be fully explored. In this paper, we establish a theoretical result for the limitations caused by quantum encoding and point out the existence of a concentration phenomenon in amplitude encoding. Compared to prior work, our theoretical result operates under more general conditions and leads to a stronger conclusion. This concentration phenomenon causes the classification predictions to remain close to random guessing, regardless of the training process. Our findings shed new light on a long-standing puzzle in the field of QML: why some QML models perform well on simple datasets like MNIST but fail to generalize to more complex practical tasks. By highlighting the pivotal role of encoding design in QML, our work clearly indicates that future research needs to focus more on the design of classical data encoding to advance the effectiveness of QML.

Variational quantum algorithms (VQAs) rely on gradient-based optimization over parameterized circuits whose loss landscape lives on a manifold of quantum states. Quantum natural gradient (QNG) accounts for this geometry through the quantum Fisher information matrix (QFIM). However, estimating the full QFIM is prohibitively expensive within practical quantum circuit shot budgets. Existing tractable approximations either discard inter-block couplings, as in block-diagonal QNG, or replace the QFIM with a measurement-induced classical Fisher surrogate, as in random natural gradient (RNG). We propose a locality-aware surrogate that targets the QFIM through its covariance representation in terms of propagated generators, retaining a structured subset of informative cross-parameter couplings while remaining practical to estimate under finite-shot budgets. Our construction combines three ingredients: weight-$k$ Pauli truncation to control estimation variance, support-overlap masking to exploit sparsity, and single-dataset classical-shadow estimation that reuses the same shadow dataset across all retained metric entries. Truncation level $k$ provides a bias--variance tradeoff: larger $k$ captures more of the propagated-generator structure but increases estimation cost, making it a budget-constrained design choice. Circuit parameters whose truncated generators remain nonzero form an active set receiving surrogate-QNG updates, while the rest follow standard gradient descent. We provide finite-shot concentration bounds for the shadow-estimated surrogate and convergence guarantees to a stationary neighborhood under standard smoothness assumptions. Experiments on variational quantum eigensolver (VQE) instances with local ans\"atze for Heisenberg and Ising spin chains show improved convergence per cumulative shot relative to SGD, Adam, block-diagonal QNG, and RNG baselines under finite-shot budgets, including on systems up to 16 qubits.