Quantum metric learning enhances machine learning by mapping classical data to a quantum Hilbert space with maximal separation between classes. However, on current NISQ hardware, this mapping process itself is prone to errors and could be fundamentally incorrect. Verifying that a quantum embedding model successfully achieves its promised separation is essential to ensure the correctness and reliability. In this paper, we propose a practical black-box verification protocol to audit the performance of quantum metric learning models. We define a setting with two parties: a powerful but untrusted prover, who claims to have a parameterized unitary circuit that embeds classical data from different groups with a guaranteed angular separation, and a limited verifier, whose quantum capabilities are restricted to performing only basic measurements. The verifier has no knowledge of the implementation of the prover, including the structure of the model, its parameters, or the details of the prover measurement setup. To verify the separation between different data groups, the proposed algorithm must overcome two key challenges. First, the verifier is ignorant of the prover's implementation details, such as the optimization cost function and measurement setup. Consequently, the verifier lacks any prior information about the expected quantum embedding states for each group. Second, the destructive nature of quantum measurements prevents direct estimation of the separation angles. Our algorithm successfully overcomes these challenges, enabling the verifier to accurately estimate the true separation angles between the different groups. We implemented the proposed protocol and deployed it to verify the QAOAEmbedding models. The results from both theoretical analysis and practical implementation show that our proposal effectively assesses embedding quality and remains robust in adversarial settings. less

Trotter decomposition provides a simple approach to simulating open quantum systems by decomposing the Lindbladian into a sum of individual terms. While it is established that Trotter errors in Hamiltonian simulation depend on nested commutators of the summands, such a relationship remains poorly understood for Lindbladian dynamics. In this Letter, we derive commutator-based Trotter error bounds for Lindbladian simulation, yielding an $O(\sqrt{N})$ scaling in the number of Trotter steps for locally interacting systems on $N$ sites. When estimating observable averages, we apply Richardson extrapolation to achieve polylogarithmic precision while maintaining the commutator scaling. To bound the extrapolation remainder, we develop a general truncation bound for the Baker-Campbell-Hausdorff expansion that bypasses common convergence issues in physically relevant systems. For local Lindbladians, our results demonstrate that the Trotter-based methods outperform prior simulation techniques in system-size scaling while requiring only $O(1)$ ancillas. Numerical simulations further validate the predicted system-size and precision scaling. less

We introduce Exchange Quantum Polynomial Time (XQP) circuits, which comprise quantum computation using only computational basis SPAM and the isotropic Heisenberg exchange interaction. Structurally, this sub-universal model captures decoherence-free subspace computation without access to singlet states. We show that XQP occupies an intermediate position between BPP and BQP, as its efficient multiplicative-error simulation would collapse the polynomial hierarchy to its third level. We further provide evidence that additive-error simulation of XQP would enable efficient additive-error simulation of arbitrary BQP computations. Remarkably, the restricted family of XQP circuits consisting solely of $\sqrt{\mathrm{SWAP}}$ gates remains hard to simulate to multiplicative error. We additionally prove that circuits generated by $\sqrt{\mathrm{SWAP}}$ gates are semi-universal, generate $t$-designs for the uniform distribution over $SU(2)$-invariant unitaries, and maximise the entangling power within XQP. Finally, we derive structural results linking computational basis states in XQP to the Gelfand-Tsetlin basis of the symmetric group, and expressing XQP output probabilities as partition functions of the six-vertex and Potts models. Our findings indicate that XQP circuits are naturally suited to near-term hardware and provide a promising platform for experimental demonstrations of quantum computational advantage. less

Quantum computers have the potential to perform computational tasks beyond the reach of classical machines. A prominent example is Shor's algorithm for integer factorization and discrete logarithms, which is of both fundamental importance and practical relevance to cryptography. However, due to the high overhead of quantum error correction, optimized resource estimates for cryptographically relevant instances of Shor's algorithm require millions of physical qubits. Here, by leveraging advances in high-rate quantum error-correcting codes, efficient logical instruction sets, and circuit design, we show that Shor's algorithm can be executed at cryptographically relevant scales with as few as 10,000 reconfigurable atomic qubits. Increasing the number of physical qubits improves time efficiency by enabling greater parallelism; under plausible assumptions, the runtime for discrete logarithms on the P-256 elliptic curve could be just a few days for a system with 26,000 physical qubits, while the runtime for factoring RSA-2048 integers is one to two orders of magnitude longer. Recent neutral-atom experiments have demonstrated universal fault-tolerant operations below the error-correction threshold, computation on arrays of hundreds of qubits, and trapping arrays with more than 6,000 highly coherent qubits. Although substantial engineering challenges remain, our theoretical analysis indicates that an appropriately designed neutral-atom architecture could support quantum computation at cryptographically relevant scales. More broadly, these results highlight the capability of neutral atoms for fault-tolerant quantum computing with wide-ranging scientific and technological applications. less

Gaussian baths are widely used to model non-Markovian environments, yet the cost of accurate simulation at long times remains poorly understood, especially when spectral densities exhibit nonanalytic behavior as in a range of realistic models. We rigorously bound the complexity of representing bath correlation functions on a time interval $[0,T]$ by sums of complex exponentials, as employed in recent variants of pseudomode and hierarchical equations of motion methods. These bounds make explicit the dependence on the maximal simulation time $T$, inverse temperature $β$, and the type and strength of singularities in an effective spectral density. For a broad class of spectral densities, the required number of exponentials is bounded independently of $T$, achieving time-uniform complexity. The $T$-dependence emerges only as polylogarithmic factors for spectral densities with strong singularities, such as step discontinuities and inverse power-law divergences. The temperature dependence is mild for bosonic environments and disappears entirely for fermionic environments. Thus, the true bottleneck for long-time simulation is not the simulation duration itself, but rather the presence of sharp nonanalytic features in the bath spectrum. Our results are instructive both for long-time simulation of non-Markovian open quantum systems, as well as for Markovian embeddings of classical generalized Langevin equations with memory kernels. less

Quantum Key Distribution (QKD) protocols require Information-Theoretically Secure (ITS) authentication of the classical channel to preserve the unconditional security of the distilled key. Standard ITS schemes are based on one-time keys: once a key is used to authenticate a message, it must be discarded. Since QKD requires mutual authentication, two independent one-time keys are typically consumed per round, imposing a non-trivial overhead on the net secure key rate. In this work, we present the authentication-with-response scheme, a novel ITS authentication scheme based on $\varepsilon$-Almost Strongly Universal$_2$ ($\varepsilon$-ASU$_2$) functions, whose IT security can be established in the Universal Composability (UC) framework. The scheme achieves mutual authentication consuming a single one-time key per QKD round, halving key consumption compared to the state-of-the-art. less

Time-local generators of open quantum systems are generically divergent at long times, even though the reduced dynamics remains regular. We construct, by analytic continuation, nonperturbative dynamical maps consistent with these generators. For the weak-coupling unbiased spin--boson model, this construction yields an explicit dynamical map that nonperturbatively resums the TCL generator and exposes how the divergences signal the approach to a singular time at which the reduced dynamics becomes noninvertible. The reconstructed map is validated against TEMPO simulations at short times and the exactly solvable rotating-wave model at all times. In the full spin--boson model, the same continuum mechanism produces both an early-time anisotropy, with a measurable phase shift that provides a signature of the environmental correlation and the pointer direction, and a late-time singularity at which the reduced dynamics becomes noninvertible. By contrast, in the rotating-wave model the map approaches this point without reaching it and remains invertible at all times. These results establish a nonperturbative framework for reconstructing reduced dynamics from divergent time-local generators, diagnosing the onset of noninvertibility, and identifying experimentally accessible early-time signatures of environment-induced anisotropy. less

The computation of thermal properties of quantum many-body systems is a central challenge in our understanding of quantum mechanics. We introduce the Quantum Finite Temperature Lanczos Method (QFTLM), which extends the finite-temperature Lanczos method to quantum computers by combining real-time quantum Krylov methods with efficient preparation of typical states for trace estimation. This approach enables the computation of thermal expectation values while avoiding the exponential scaling inherent to classical exact simulation techniques. Numerical experiments on the transverse-field Ising model show that QFTLM can reproduce thermal observables over a wide temperature range. We further analyze the influence of Krylov dimension, number of trace-estimator states, and Trotter error, and show that suitable regularization is essential for robustness in noisy settings. These results establish QFTLM as a promising framework for finite-temperature quantum simulation. less

Capturing the dynamics of quantum many-body systems under time-dependent driving protocols is a central challenge for numerical simulations. Existing methods such as tensor networks and time-dependent neural quantum states, however, must be re-run for every protocol. In this work, we introduce the Neural Operator Quantum State (NOQS) as a foundation model for quantum dynamics. Rather than solving the Schrödinger equation for individual trajectories, our approach aims to \emph{learn the solution operator} that maps entire driving protocols to time-evolved quantum states. Once trained, the NOQS predicts time evolution under unseen protocols in a single forward pass, requiring no additional optimization. We validate NOQS on the two-dimensional Ising model with time-dependent longitudinal and transverse fields, demonstrating accurate prediction not only for unseen in-distribution protocols, but also for qualitatively different, out-of-distribution functional forms of driving. Further, a single NOQS model can be transferred between different temporal resolutions, and can be efficiently fine-tuned with sparse experimental measurements to improve predictions across all observables at negligible cost. Our work introduces a new paradigm for quantum dynamics simulation and provides a practical computational-experimental interface for driven quantum systems. less

Importance sampling based on quasi-probability decomposition is the backbone of many widely used techniques, such as error mitigation, circuit knitting, and, more generally, virtual quantum resource distillation, as it allows one to simulate operations that are not accessible in a given setting. However, this class of protocols faces a fundamental problem -- it only allows to estimate expectation values. Here, we provide a general framework that lifts any quasi-probability-based protocol from expectation value estimation to a weak simulator, realizing sampling from the desired distribution only using a restricted class of quantum resources. Our method runs with the sampling cost proportional to the negativity of the quasi-probability, in stark contrast to the naive estimation-based approach that requires a large number of samples even in the case of small negativity. We show that our method requires significantly fewer samples in a number of relevant scenarios, such as error mitigation, entanglement distillation and magic state distillation. Our framework realizes the weak simulation of quantum resources without actually distilling the state, introducing a new notion of quantum resource distillation. less