Showing 1–46 of 46 results for author: Tong, Y

Efficient Classical Simulation of Weakly Interacting Fermion Dynamics

Authors: Chu Zhao, Iman Marvian, Yu Tong

Abstract: We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable $A$ at time $t$. By analyzing the convergence of the perturbative expansion in the interaction strength $λ$ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation va… ▽ More We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable $A$ at time $t$. By analyzing the convergence of the perturbative expansion in the interaction strength $λ$ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime $λ|t|^{2D+1}=\mathcal{O}(1)$, when the Hamiltonian is geometrically local on a $D$-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to $λ|t|=\mathcal{O}(1)$ with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to $λ|t|=\mathcal{O}(1)$, modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable. △ Less

Submitted 19 August, 2026; originally announced August 2026.

Exact Hilbert-space ergodicity from continuous monitoring

Authors: Yue Wu, Yuzhi Tong, Liang Mao, Pengfei Zhang

Abstract: Quantum evolution is generally expected to drive a quantum many-body system toward equilibrium. This expectation is often justified by the Hilbert-space ergodicity of generic quantum dynamics, namely, the idea that pure-state evolution explores Hilbert space uniformly up to physical constraints. Such a statement can be made rigorous by requiring the associated state ensemble to form the Haar-rando… ▽ More Quantum evolution is generally expected to drive a quantum many-body system toward equilibrium. This expectation is often justified by the Hilbert-space ergodicity of generic quantum dynamics, namely, the idea that pure-state evolution explores Hilbert space uniformly up to physical constraints. Such a statement can be made rigorous by requiring the associated state ensemble to form the Haar-random ensemble, or its more structured generalization, the Scrooge ensemble. In this Letter, we report the emergence of exact Hilbert-space ergodicity in a continuously monitored quantum many-body system. For any target density matrix $σ$, we construct a continuously monitored system for which we rigorously prove that the Scrooge ensemble of $σ$ is the unique late-time equilibrium distribution of quantum trajectories. Remarkably, this requires only that the jump operators in the monitoring form a deformed unitary 1-design, a seemingly much weaker condition than full ergodicity. We numerically demonstrate our predictions by simulating continuously monitored systems whose equilibrium states are thermal states. Our results establish a rigorous mechanism for the emergence of Hilbert-space ergodicity and provide a practical route for its investigation on quantum devices. △ Less

Submitted 30 June, 2026; v1 submitted 27 June, 2026; originally announced June 2026.

Bridging Krylov Complexity and Universal Analog Quantum Simulator

Authors: Shuo Zhang, Yuzhi Tong, Pengfei Zhang, Zeyu Liu

Abstract: Quantum simulation of complex many-body systems beyond classical computational capabilities provides a promising route toward understanding novel quantum phases and their transitions. In particular, analog quantum simulators with global control fields have attracted considerable attention due to their potential to simulate arbitrary Hamiltonians and perform quantum computing tasks. However, a clea… ▽ More Quantum simulation of complex many-body systems beyond classical computational capabilities provides a promising route toward understanding novel quantum phases and their transitions. In particular, analog quantum simulators with global control fields have attracted considerable attention due to their potential to simulate arbitrary Hamiltonians and perform quantum computing tasks. However, a clear, quantitative measure for the complexity of implementing specific quantum operations in such systems is still lacking. In this Letter, we address this challenge by introducing generalized Krylov complexity, a concept originating from operator growth dynamics, as a direct diagnosis for this synthesis complexity. We construct the block Krylov basis generated by a set of Hamiltonians, which naturally organizes the operator space achievable through the simulator's native interactions and their nested commutators. By analyzing representative systems including Rydberg atom arrays, we demonstrate that the generalized Krylov complexity of a target operation serves as a strong predictor of the minimum time required for its realization. Our results establish Krylov complexity as an intuitive and predictive tool for designing efficient control protocols in analog quantum simulators. △ Less

Submitted 8 May, 2026; originally announced May 2026.

Comments: 9 pages, 4 figures

Quantum Gibbs sampling through the detectability lemma

Authors: Di Fang, Jianfeng Lu, Yu Tong, Chu Zhao

Abstract: Gibbs state preparation is an important subroutine in quantum computing. In this work we use the detectability lemma to improve Gibbs state preparation. Specifically, we design new Gibbs state preparation methods that do not rely on simulating Lindbladian evolution, thus avoiding the overhead from it. For local Lindbladians consisting of $M$ terms, this approach reduces the cost by a factor of… ▽ More Gibbs state preparation is an important subroutine in quantum computing. In this work we use the detectability lemma to improve Gibbs state preparation. Specifically, we design new Gibbs state preparation methods that do not rely on simulating Lindbladian evolution, thus avoiding the overhead from it. For local Lindbladians consisting of $M$ terms, this approach reduces the cost by a factor of $O(M)$. We also combine the detectability lemma operator and quantum singular value transformation to implement ground state projection operators of frustration-free Hamiltonians, resulting in a quadratic speedup in the spectral gap dependence. Applying this method to Lindbladians for the Gibbs state of local commuting Hamiltonians, we achieve quadratically better dependence on the Lindbladian spectral gap. △ Less

Submitted 8 April, 2026; originally announced April 2026.

Autonomous Hamiltonian certification and changepoint detection

Authors: Steven T. Flammia, Dmitrii Khitrin, Muzhou Ma, Jamie Sikora, Yu Tong, Alice Zheng

Abstract: Modern quantum devices require high-precision Hamiltonian dynamics, but environmental noise can cause calibrated Hamiltonian parameters to drift over time, necessitating expensive recalibration. Detecting when recalibration is needed is challenging, especially since the very gates required for sophisticated verification protocols may themselves be miscalibrated. While cloud quantum computing servi… ▽ More Modern quantum devices require high-precision Hamiltonian dynamics, but environmental noise can cause calibrated Hamiltonian parameters to drift over time, necessitating expensive recalibration. Detecting when recalibration is needed is challenging, especially since the very gates required for sophisticated verification protocols may themselves be miscalibrated. While cloud quantum computing services implement heuristic routines for triggering recalibration, the fundamental limits of optimal recalibration are not yet known. We develop efficient Hamiltonian certification and changepoint detection protocols in the autonomous setting, where we cannot rely on an external noiseless device and use only single-qubit gates and measurements, making the protocols robust to the calibration issues for multi-qubit operations they aim to detect. For unknown $n$-qubit Hamiltonians $H$ and $H_0$ with operator norm bounded by $M$, our certification protocol distinguishes whether $\|H-H_0\|_F\geqε$ or $\|H-H_0\|_F\leq O(ε/\sqrt{n})$ with sample complexity $O(nM^2\ln(1/δ)/ε^2)$ and total evolution time $O(nM\ln(1/δ)/ε^2)$. We achieve this by evolving random stabilizer product states and performing adaptive single-qubit measurements based on a classically simulable hypothesis state. Extending this to continuous monitoring, we develop an online changepoint detection algorithm using the CUSUM procedure that achieves a detection delay time bound of $O(nM\ln(M\mathbb{E}_\infty[T])/ε^2)$, matching the known asymptotically optimal scaling with respect to false alarm run time $\mathbb{E}_\infty[T]$. Our approach enables quantum devices to autonomously monitor their own calibration status without requiring ancillary systems, entangling operations, or a trusted reference device, offering a practical solution for robust quantum computing with contemporary noisy devices. △ Less

Submitted 27 March, 2026; originally announced March 2026.

Comments: 26 pages, 4 figures. Comments welcome

Learning Hamiltonians in the Heisenberg limit with static single-qubit fields

Authors: Shrigyan Brahmachari, Shuchen Zhu, Iman Marvian, Yu Tong

Abstract: Learning the Hamiltonian governing a quantum system is a central task in quantum metrology, sensing, and device characterization. Existing Heisenberg-limited Hamiltonian learning protocols either require multi-qubit operations that are prone to noise, or single-qubit operations whose frequency or strength increases with the desired precision. These two requirements limit the applicability of Hamil… ▽ More Learning the Hamiltonian governing a quantum system is a central task in quantum metrology, sensing, and device characterization. Existing Heisenberg-limited Hamiltonian learning protocols either require multi-qubit operations that are prone to noise, or single-qubit operations whose frequency or strength increases with the desired precision. These two requirements limit the applicability of Hamiltonian learning on near-term quantum platforms. We present a protocol that learns a quantum Hamiltonian with the optimal Heisenberg-limited scaling using only single-qubit control in the form of static fields with strengths that are independent of the target precision. Our protocol is robust against the state preparation and measurement (SPAM) error. By overcoming these limitations, our protocol provides new tools for device characterization and quantum sensing. We demonstrate that our method achieves the Heisenberg-limited scaling through rigorous mathematical proof and numerical experiments. We also prove an information-theoretic lower bound showing that a non-vanishing static field strength is necessary for achieving the Heisenberg limit unless one employs an extensive number of discrete control operations. △ Less

Submitted 15 January, 2026; originally announced January 2026.

Self-Supervised Learning with Noisy Dataset for Rydberg Microwave Sensors Denoising

Authors: Zongkai Liu, Qiming Ren, Wenguang Yang, Yanjie Tong, Huizhen Wang, Yijie Zhang, Ruohao Zhi, Junyao Xie, Mingyong Jing, Hao Zhang, Liantuan Xiao, Suotang Jia, Ke Tang, Linjie Zhang

Abstract: We report a self-supervised deep learning framework for Rydberg sensors that enables single-shot noise suppression matching the accuracy of multi-measurement averaging. The framework eliminates the need for clean reference signals (hardly required in quantum sensing) by training on two sets of noisy signals with identical statistical distributions. When evaluated on Rydberg sensing datasets, the f… ▽ More We report a self-supervised deep learning framework for Rydberg sensors that enables single-shot noise suppression matching the accuracy of multi-measurement averaging. The framework eliminates the need for clean reference signals (hardly required in quantum sensing) by training on two sets of noisy signals with identical statistical distributions. When evaluated on Rydberg sensing datasets, the framework outperforms wavelet transform and Kalman filtering, achieving a denoising effect equivalent to 10,000-set averaging while reducing computation time by three orders of magnitude. We further validate performance across diverse noise profiles and quantify the complexity-performance trade-off of U-Net and Transformer architectures, providing actionable guidance for optimizing deep learning-based denoising in Rydberg sensor systems. △ Less

Submitted 5 January, 2026; originally announced January 2026.

Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions

Authors: Hongrui Chen, Cambyse Rouzé, Jielun Chen, Jiaqing Jiang, Samuel O. Scalet, Yongtao Zhan, Garnet Kin-Lic Chan, Lexing Ying, Yu Tong

Abstract: We propose a randomized algorithm to compute the log-partition function of weakly interacting fermions with polynomial runtime in both the system size and precision. Although weakly interacting fermionic systems are considered tractable for many computational methods such as the diagrammatic quantum Monte Carlo, a mathematically rigorous proof of polynomial runtime has been lacking. In this work w… ▽ More We propose a randomized algorithm to compute the log-partition function of weakly interacting fermions with polynomial runtime in both the system size and precision. Although weakly interacting fermionic systems are considered tractable for many computational methods such as the diagrammatic quantum Monte Carlo, a mathematically rigorous proof of polynomial runtime has been lacking. In this work we first extend the proof techniques developed in previous works for proving the convergence of the cumulant expansion in periodic systems to the non-periodic case. A key equation used to analyze the sum of connected Feynman diagrams, which we call the tree-determinant expansion, reveals an underlying tree structure in the summation. This enables us to design a new randomized algorithm to compute the log-partition function through importance sampling augmented by belief propagation. This approach differs from the traditional method based on Markov chain Monte Carlo, whose efficiency is hard to guarantee, and enables us to obtain a algorithm with provable polynomial runtime. △ Less

Submitted 12 December, 2025; originally announced December 2025.

Time series learning in a many-body Rydberg system with emergent collective amplification

Authors: Zongkai Liu, Qiming Ren, Chris Nill, Albert Cabot, Wei Xia, Yanjie Tong, Huizhen Wang, Wenguang Yang, Junyao Xie, Mingyong Jing, Hao Zhang, Liantuan Xiao, Suotang Jia, Igor Lesanovsky, Linjie Zhang

Abstract: Interacting Rydberg atoms constitute a versatile platform for the realization of non-equilibrium states of matter. Close to phase transitions, they respond collectively to external perturbations, which can be harnessed for technological applications in the domain of quantum metrology and sensing. Owing to the controllable complexity and straightforward interpretability of Rydberg atoms, we can obs… ▽ More Interacting Rydberg atoms constitute a versatile platform for the realization of non-equilibrium states of matter. Close to phase transitions, they respond collectively to external perturbations, which can be harnessed for technological applications in the domain of quantum metrology and sensing. Owing to the controllable complexity and straightforward interpretability of Rydberg atoms, we can observe and tune the emergent collective amplification. Here, we investigate the application of an interacting Rydberg vapour for the purpose of time series prediction. The vapour is driven by a laser field whose Rabi frequency is modulated in order to input the time series. We find that close to a non-equilibrium phase transition, where collective effects are amplified, the capability of the system to learn the input becomes enhanced. This is reflected in an increase of the accuracy with which future values of the time series can be predicted. Using the Lorenz time series and temperature data as examples, our work demonstrates how emergent phenomena enhance the capability of noisy many-body systems for data processing and forecasting. △ Less

Submitted 2 June, 2026; v1 submitted 18 November, 2025; originally announced November 2025.

Comments: Z.L, Q.R, and C.N contribute equally to this work

Improved Hamiltonian learning and sparsity testing through Bell sampling

Authors: Savar D. Sinha, Yu Tong

Abstract: We consider the problem of learning an $M$-sparse Hamiltonian and the related problem of Hamiltonian sparsity testing. Through a detailed analysis of Bell sampling, we reduce the total evolution time required by the state-of-the-art algorithm for $M$-sparse Hamiltonian learning to $\widetilde{\mathcal{O}}(M/ε)$, where $ε$ denotes the $\ell^{\infty}$ error, achieving an improvement by a factor of… ▽ More We consider the problem of learning an $M$-sparse Hamiltonian and the related problem of Hamiltonian sparsity testing. Through a detailed analysis of Bell sampling, we reduce the total evolution time required by the state-of-the-art algorithm for $M$-sparse Hamiltonian learning to $\widetilde{\mathcal{O}}(M/ε)$, where $ε$ denotes the $\ell^{\infty}$ error, achieving an improvement by a factor of $M$ (ignoring the logarithmic factor) while only requiring access to forward time-evolution. We then establish a connection between Hamiltonian learning and Hamiltonian sparsity testing through Bell sampling, which enables us to propose a Hamiltonian sparsity testing with state-of-the-art total evolution time scaling. △ Less

Submitted 9 September, 2025; originally announced September 2025.

Qubit-Efficient Quantum Algorithm for Linear Differential Equations

Authors: Di Fang, David Lloyd George, Yu Tong

Abstract: As quantum hardware rapidly advances toward the early fault-tolerant era, a key challenge is to develop quantum algorithms that are not only theoretically sound but also hardware-friendly on near-term devices. In this work, we propose a quantum algorithm for solving linear ordinary differential equations (ODEs) with a provable runtime guarantee. Our algorithm uses only a single ancilla qubit, and… ▽ More As quantum hardware rapidly advances toward the early fault-tolerant era, a key challenge is to develop quantum algorithms that are not only theoretically sound but also hardware-friendly on near-term devices. In this work, we propose a quantum algorithm for solving linear ordinary differential equations (ODEs) with a provable runtime guarantee. Our algorithm uses only a single ancilla qubit, and is locality preserving, i.e., when the coefficient matrix of the ODE is $k$-local, the algorithm only needs to implement the time evolution of $(k+1)$-local Hamiltonians. We also discuss the connection between our proposed algorithm and Lindbladian simulation. By applying our algorithm to the interacting Hatano-Nelson model, a widely studied non-Hermitian model with rich phenomenology, and numerically simulating it under realistic noise models, we demonstrate its practical feasibility on near-term quantum devices. △ Less

Submitted 11 August, 2026; v1 submitted 22 July, 2025; originally announced July 2025.

Heisenberg-limited Hamiltonian learning continuous variable systems via engineered dissipation

Authors: Tim Möbus, Andreas Bluhm, Tuvia Gefen, Yu Tong, Albert H. Werner, Cambyse Rouzé

Abstract: Discrete and continuous variables oftentimes require different treatments in many learning tasks. Identifying the Hamiltonian governing the evolution of a quantum system is a fundamental task in quantum learning theory. While previous works mostly focused on quantum spin systems, where quantum states can be seen as superpositions of discrete bit-strings, relatively little is known about Hamiltonia… ▽ More Discrete and continuous variables oftentimes require different treatments in many learning tasks. Identifying the Hamiltonian governing the evolution of a quantum system is a fundamental task in quantum learning theory. While previous works mostly focused on quantum spin systems, where quantum states can be seen as superpositions of discrete bit-strings, relatively little is known about Hamiltonian learning for continuous-variable quantum systems. In this work we focus on learning the Hamiltonian of a bosonic quantum system, a common type of continuous-variable quantum system. This learning task involves an infinite-dimensional Hilbert space and unbounded operators, making mathematically rigorous treatments challenging. We introduce an analytic framework to study the effects of strong dissipation in such systems, enabling a rigorous analysis of cat qubit stabilization via engineered dissipation. This framework also supports the development of Heisenberg-limited algorithms for learning general bosonic Hamiltonians with higher-order terms of the creation and annihilation operators. Notably, our scheme requires a total Hamiltonian evolution time that scales only logarithmically with the number of modes and inversely with the precision of the reconstructed coefficients. On a theoretical level, we derive a new quantitative adiabatic approximation estimate for general Lindbladian evolutions with unbounded generators. Finally, we discuss possible experimental implementations. △ Less

Submitted 31 May, 2025; originally announced June 2025.

High-Temperature Fermionic Gibbs States are Mixtures of Gaussian States

Authors: Akshar Ramkumar, Yiyi Cai, Yu Tong, Jiaqing Jiang

Abstract: Efficient simulation of a quantum system generally relies on structural properties of the quantum state. Motivated by the recent results by Bakshi et al. on the sudden death of entanglement in high-temperature Gibbs states of quantum spin systems, we study the high-temperature Gibbs states of bounded-degree local fermionic Hamiltonians, which include the special case of geometrically local fermion… ▽ More Efficient simulation of a quantum system generally relies on structural properties of the quantum state. Motivated by the recent results by Bakshi et al. on the sudden death of entanglement in high-temperature Gibbs states of quantum spin systems, we study the high-temperature Gibbs states of bounded-degree local fermionic Hamiltonians, which include the special case of geometrically local fermionic systems. We prove that at a sufficiently high temperature that is independent of the system size, the Gibbs state is a probabilistic mixture of fermionic Gaussian states. This forms the basis of an efficient classical algorithm to prepare the Gibbs state by sampling from a distribution of fermionic Gaussian states. As a contrasting example, we show that high-temperature Gibbs states of the Sachdev-Ye-Kitaev (SYK) model are not convex mixtures of Gaussian states. △ Less

Submitted 17 January, 2026; v1 submitted 14 May, 2025; originally announced May 2025.

Comments: 46 pages; new counterexample

State-space gradient descent and metastability in quantum systems

Authors: Shuchen Zhu, Yu Tong

Abstract: We propose a quantum algorithm, inspired by ADAPT-VQE, to variationally prepare the ground state of a quantum Hamiltonian, with the desirable property that if it fails to find the ground state, it still yields a physically meaningful local-minimum state that oftentimes corresponds to a metastable state of the quantum system. At each iteration, our algorithm reduces the energy using a set of local… ▽ More We propose a quantum algorithm, inspired by ADAPT-VQE, to variationally prepare the ground state of a quantum Hamiltonian, with the desirable property that if it fails to find the ground state, it still yields a physically meaningful local-minimum state that oftentimes corresponds to a metastable state of the quantum system. At each iteration, our algorithm reduces the energy using a set of local physical operations. The operations to perform are chosen using gradient and Hessian information that can be efficiently extracted from experiments. We show that our algorithm does not suffer from the barren plateau problem, which is a significant issue in many variational quantum algorithms. We use numerical simulation to demonstrate that our method reliably produces either the true ground state or a physically meaningful metastable state in typical physical systems with such states. △ Less

Submitted 14 May, 2025; originally announced May 2025.

Ansatz-free Hamiltonian learning with Heisenberg-limited scaling

Authors: Hong-Ye Hu, Muzhou Ma, Weiyuan Gong, Qi Ye, Yu Tong, Steven T. Flammia, Susanne F. Yelin

Abstract: Learning the unknown interactions that govern a quantum system is crucial for quantum information processing, device benchmarking, and quantum sensing. The problem, known as Hamiltonian learning, is well understood under the assumption that interactions are local, but this assumption may not hold for arbitrary Hamiltonians. Previous methods all require high-order inverse polynomial dependency with… ▽ More Learning the unknown interactions that govern a quantum system is crucial for quantum information processing, device benchmarking, and quantum sensing. The problem, known as Hamiltonian learning, is well understood under the assumption that interactions are local, but this assumption may not hold for arbitrary Hamiltonians. Previous methods all require high-order inverse polynomial dependency with precision, unable to surpass the standard quantum limit and reach the gold standard Heisenberg-limited scaling. Whether Heisenberg-limited Hamiltonian learning is possible without prior assumptions about the interaction structures, a challenge we term \emph{ansatz-free Hamiltonian learning}, remains an open question. In this work, we present a quantum algorithm to learn arbitrary sparse Hamiltonians without any structure constraints using only black-box queries of the system's real-time evolution and minimal digital controls to attain Heisenberg-limited scaling in estimation error. Our method is also resilient to state-preparation-and-measurement errors, enhancing its practical feasibility. We numerically demonstrate our ansatz-free protocol for learning physical Hamiltonians and validating analog quantum simulations, benchmarking our performance against the state-of-the-art Heisenberg-limited learning approach. Moreover, we establish a fundamental trade-off between total evolution time and quantum control on learning arbitrary interactions, revealing the intrinsic interplay between controllability and total evolution time complexity for any learning algorithm. These results pave the way for further exploration into Heisenberg-limited Hamiltonian learning in complex quantum systems under minimal assumptions, potentially enabling new benchmarking and verification protocols. △ Less

Submitted 30 June, 2025; v1 submitted 17 February, 2025; originally announced February 2025.

Comments: Updated version with expanded explanations, added pseudocode, and new numerical demonstrations. 10 pages, 4 figures. HYH and MM contributed equally

Journal ref: PRX Quantum 6, 040315 (2025)

Fast mixing of weakly interacting fermionic systems at any temperature

Authors: Yu Tong, Yongtao Zhan

Abstract: We study the mixing time of a recently proposed efficiently implementable Lindbladian designed to prepare the Gibbs states in the setting of weakly interacting fermionic systems. We show that at any temperature, the Lindbladian spectral gap for even parity observables is lower bounded by a constant that is independent of the system size, when the interaction strength (e.g., the on-site interaction… ▽ More We study the mixing time of a recently proposed efficiently implementable Lindbladian designed to prepare the Gibbs states in the setting of weakly interacting fermionic systems. We show that at any temperature, the Lindbladian spectral gap for even parity observables is lower bounded by a constant that is independent of the system size, when the interaction strength (e.g., the on-site interaction strength for the Fermi-Hubbard model) is below a constant threshold, which is also independent of the system size. This leads to a mixing time estimate that is at most linear in the system size, thus showing that the corresponding Gibbs states can be prepared efficiently on quantum computers. △ Less

Submitted 20 January, 2025; v1 submitted 31 December, 2024; originally announced January 2025.

Learning $k$-body Hamiltonians via compressed sensing

Authors: Muzhou Ma, Steven T. Flammia, John Preskill, Yu Tong

Abstract: We study the problem of learning a $k$-body Hamiltonian with $M$ unknown Pauli terms that are not necessarily geometrically local. We propose a protocol that learns the Hamiltonian to precision $ε$ with total evolution time ${\mathcal{O}}(M^{1/2+1/p}/ε)$ up to logarithmic factors, where the error is quantified by the $\ell^p$-distance between Pauli coefficients. Our learning protocol uses only sin… ▽ More We study the problem of learning a $k$-body Hamiltonian with $M$ unknown Pauli terms that are not necessarily geometrically local. We propose a protocol that learns the Hamiltonian to precision $ε$ with total evolution time ${\mathcal{O}}(M^{1/2+1/p}/ε)$ up to logarithmic factors, where the error is quantified by the $\ell^p$-distance between Pauli coefficients. Our learning protocol uses only single-qubit control operations and a GHZ state initial state, is non-adaptive, is robust against SPAM errors, and performs well even if $M$ and $k$ are not precisely known in advance or if the Hamiltonian is not exactly $M$-sparse. Methods from the classical theory of compressed sensing are used for efficiently identifying the $M$ terms in the Hamiltonian from among all possible $k$-body Pauli operators. We also provide a lower bound on the total evolution time needed in this learning task, and we discuss the operational interpretations of the $\ell^1$ and $\ell^2$ error metrics. In contrast to most previous works, our learning protocol requires neither geometric locality nor any other relaxed locality conditions. △ Less

Submitted 11 December, 2024; v1 submitted 24 October, 2024; originally announced October 2024.

Comments: 49 pages, 1 figure

Rapid initial state preparation for the quantum simulation of strongly correlated molecules

Authors: Dominic W. Berry, Yu Tong, Tanuj Khattar, Alec White, Tae In Kim, Sergio Boixo, Lin Lin, Seunghoon Lee, Garnet Kin-Lic Chan, Ryan Babbush, Nicholas C. Rubin

Abstract: Studies on quantum algorithms for ground state energy estimation often assume perfect ground state preparation; however, in reality the initial state will have imperfect overlap with the true ground state. Here we address that problem in two ways: by faster preparation of matrix product state (MPS) approximations, and more efficient filtering of the prepared state to find the ground state energy.… ▽ More Studies on quantum algorithms for ground state energy estimation often assume perfect ground state preparation; however, in reality the initial state will have imperfect overlap with the true ground state. Here we address that problem in two ways: by faster preparation of matrix product state (MPS) approximations, and more efficient filtering of the prepared state to find the ground state energy. We show how to achieve unitary synthesis with a Toffoli complexity about $7 \times$ lower than that in prior work, and use that to derive a more efficient MPS preparation method. For filtering we present two different approaches: sampling and binary search. For both we use the theory of window functions to avoid large phase errors and minimise the complexity. We find that the binary search approach provides better scaling with the overlap at the cost of a larger constant factor, such that it will be preferred for overlaps less than about $0.003$. Finally, we estimate the total resources to perform ground state energy estimation of Fe-S cluster systems, including the FeMo cofactor by estimating the overlap of different MPS initial states with potential ground-states of the FeMo cofactor using an extrapolation procedure. {With a modest MPS bond dimension of 4000, our procedure produces an estimate of $\sim 0.9$ overlap squared with a candidate ground-state of the FeMo cofactor, producing a total resource estimate of $7.3 \times 10^{10}$ Toffoli gates; neglecting the search over candidates and assuming the accuracy of the extrapolation, this validates prior estimates that used perfect ground state overlap. This presents an example of a practical path to prepare states of high overlap in a challenging-to-compute chemical system. △ Less

Submitted 18 September, 2024; originally announced September 2024.

Comments: 47 pages, 20 figures

Journal ref: PRX Quantum 6, 020327 (2025)

Broadband light extraction from near-surface NV centers using crystalline-silicon antennas

Authors: Minjeong Kim, Maryam Zahedian, Wenxin Wu, Chengyu Fang, Zhaoning Yu, Raymond A. Wambold, Ricardo Vidrio, Yuhan Tong, Shenwei Yin, David A. Czaplewski, Jennifer T. Choy, Mikhail A. Kats

Abstract: We use crystalline silicon (Si) antennas to efficiently extract broadband single-photon fluorescence from shallow nitrogen-vacancy (NV) centers in diamond into free space. Our design features relatively easy-to-pattern high-index Si resonators on the diamond surface to boost photon extraction by overcoming total internal reflection and Fresnel reflection at the diamond-air interface, and providing… ▽ More We use crystalline silicon (Si) antennas to efficiently extract broadband single-photon fluorescence from shallow nitrogen-vacancy (NV) centers in diamond into free space. Our design features relatively easy-to-pattern high-index Si resonators on the diamond surface to boost photon extraction by overcoming total internal reflection and Fresnel reflection at the diamond-air interface, and providing modest Purcell enhancement, without etching or otherwise damaging the diamond surface. In simulations, ~17 times more single photons are collected from a single NV center compared to the case without the antenna; in experiments, we observe an enhancement of ~9 times, limited by spatial alignment between the NV and the antenna. Our approach can be readily applied to other color centers in diamond, and more generally to the extraction of light from quantum emitters in wide-bandgap materials. △ Less

Submitted 10 February, 2025; v1 submitted 1 September, 2024; originally announced September 2024.

Comments: Updated main text + supplementary

Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs

Authors: Jianqiang Li, Yu Tong

Abstract: Finding problems that allow for superpolynomial quantum speedup is one of the most important tasks in quantum computation. A key challenge is identifying problem structures that can only be exploited by quantum mechanics. In this paper, we find a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle, and this class of gr… ▽ More Finding problems that allow for superpolynomial quantum speedup is one of the most important tasks in quantum computation. A key challenge is identifying problem structures that can only be exploited by quantum mechanics. In this paper, we find a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle, and this class of graphs is named regular sunflower graphs. We prove that, with high probability, a regular sunflower graph of degree at least $7$ is a mild expander graph, that is, the spectral gap of the graph Laplacian is at least inverse polylogarithmic in the graph size. We provide an efficient quantum algorithm to find an $s$-$t$ path in the regular sunflower graph while any classical algorithm takes exponential time. This quantum advantage is achieved by efficiently preparing a $0$-eigenstate of the adjacency matrix of the regular sunflower graph as a quantum superposition state over the vertices, and this quantum state contains enough information to help us efficiently find an $s$-$t$ path in the regular sunflower graph. Because the security of an isogeny-based cryptosystem depends on the hardness of finding an $s$-$t$ path in an expander graph \cite{Charles2009}, a quantum speedup of the pathfinding problem on an expander graph is of significance. Our result represents a step towards this goal as the first provable exponential speedup for pathfinding in a mild expander graph. △ Less

Submitted 2 May, 2025; v1 submitted 19 July, 2024; originally announced July 2024.

Comments: 45 pages,3 figures

Mixing Time of Open Quantum Systems via Hypocoercivity

Authors: Di Fang, Jianfeng Lu, Yu Tong

Abstract: Understanding the mixing of open quantum systems is a fundamental problem in physics and quantum information science. Existing approaches for estimating the mixing time often rely on the spectral gap estimation of the Lindbladian generator, which can be challenging to obtain in practice. We propose a novel theoretical framework to estimate the mixing time of open quantum systems that treats the Ha… ▽ More Understanding the mixing of open quantum systems is a fundamental problem in physics and quantum information science. Existing approaches for estimating the mixing time often rely on the spectral gap estimation of the Lindbladian generator, which can be challenging to obtain in practice. We propose a novel theoretical framework to estimate the mixing time of open quantum systems that treats the Hamiltonian and dissipative part separately, thus circumventing the need for a priori estimation of the spectral gap of the full Lindbladian generator. This framework yields mixing time estimates for a class of quantum systems that are otherwise hard to analyze, even though it does not apply to arbitrary Lindbladians. The technique is based on the construction of an energy functional inspired by the hypocoercivity of (classical) kinetic theory. △ Less

Submitted 1 April, 2025; v1 submitted 17 April, 2024; originally announced April 2024.

Atomic magnetometry using a metasurface polarizing beamsplitter in silicon on sapphire

Authors: Xuting Yang, Pritha Mukherjee, Minjeong Kim, Hongyan Mei, Chengyu Fang, Soyeon Choi, Yuhan Tong, Sarah Perlowski, David A. Czaplewski, Alan M. Dibos, Mikhail A. Kats, Jennifer T. Choy

Abstract: We demonstrate atomic magnetometry using a metasurface polarizing beamsplitter fabricated on a silicon-on-sapphire (SOS) platform. The metasurface splits a beam that is near-resonant with the rubidium atoms (795 nm) into orthogonal linear polarizations, enabling measurement of magnetically sensitive circular birefringence in a rubidium vapor through balanced polarimetry. We incorporated the metasu… ▽ More We demonstrate atomic magnetometry using a metasurface polarizing beamsplitter fabricated on a silicon-on-sapphire (SOS) platform. The metasurface splits a beam that is near-resonant with the rubidium atoms (795 nm) into orthogonal linear polarizations, enabling measurement of magnetically sensitive circular birefringence in a rubidium vapor through balanced polarimetry. We incorporated the metasurface into an atomic magnetometer based on nonlinear magneto-optical rotation and measured sub-nanotesla sensitivity, which is limited by low-frequency technical noise and transmission loss through the metasurface. To our knowledge, this work represents the first demonstration of SOS nanophotonics for atom-based sensing and paves the way for highly integrated, miniaturized atomic sensors with enhanced sensitivity and portability. △ Less

Submitted 2 April, 2024; originally announced April 2024.

Stochastic Error Cancellation in Analog Quantum Simulation

Authors: Yiyi Cai, Yu Tong, John Preskill

Abstract: Analog quantum simulation is a promising path towards solving classically intractable problems in many-body physics on near-term quantum devices. However, the presence of noise limits the size of the system and the length of time that can be simulated. In our work, we consider an error model in which the actual Hamiltonian of the simulator differs from the target Hamiltonian we want to simulate by… ▽ More Analog quantum simulation is a promising path towards solving classically intractable problems in many-body physics on near-term quantum devices. However, the presence of noise limits the size of the system and the length of time that can be simulated. In our work, we consider an error model in which the actual Hamiltonian of the simulator differs from the target Hamiltonian we want to simulate by small local perturbations, which are assumed to be random and unbiased. We analyze the error accumulated in observables in this setting and show that, due to stochastic error cancellation, with high probability the error scales as the square root of the number of qubits instead of linearly. We explore the concentration phenomenon of this error as well as its implications for local observables in the thermodynamic limit. Moreover, we show that stochastic error cancellation also manifests in the fidelity between the target state at the end of time-evolution and the actual state we obtain in the presence of noise. This indicates that, to reach a certain fidelity, more noise can be tolerated than implied by the worst-case bound if the noise comes from many statistically independent sources. △ Less

Submitted 18 October, 2024; v1 submitted 24 November, 2023; originally announced November 2023.

Comments: 17 pages, 2 figures

Journal ref: Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 2:1-2:15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2024)

Learning conservation laws in unknown quantum dynamics

Authors: Yongtao Zhan, Andreas Elben, Hsin-Yuan Huang, Yu Tong

Abstract: We present a learning algorithm for discovering conservation laws given as sums of geometrically local observables in quantum dynamics. This includes conserved quantities that arise from local and global symmetries in closed and open quantum many-body systems. The algorithm combines the classical shadow formalism for estimating expectation values of observable and data analysis techniques based on… ▽ More We present a learning algorithm for discovering conservation laws given as sums of geometrically local observables in quantum dynamics. This includes conserved quantities that arise from local and global symmetries in closed and open quantum many-body systems. The algorithm combines the classical shadow formalism for estimating expectation values of observable and data analysis techniques based on singular value decompositions and robust polynomial interpolation to discover all such conservation laws in unknown quantum dynamics with rigorous performance guarantees. Our method can be directly realized in quantum experiments, which we illustrate with numerical simulations, using closed and open quantum system dynamics in a $\mathbb{Z}_2$-gauge theory and in many-body localized spin-chains. △ Less

Submitted 1 September, 2023; originally announced September 2023.

Comments: 22 pages, 3 figures

Robust ground-state energy estimation under depolarizing noise

Authors: Zhiyan Ding, Yulong Dong, Yu Tong, Lin Lin

Abstract: We present a novel ground-state energy estimation algorithm that is robust under global depolarizing error channels. Building upon the recently developed Quantum Exponential Least Squares (QCELS) algorithm, our new approach incorporates significant advancements to ensure robust estimation while maintaining a polynomial cost in precision. By leveraging the spectral gap of the Hamiltonian effectivel… ▽ More We present a novel ground-state energy estimation algorithm that is robust under global depolarizing error channels. Building upon the recently developed Quantum Exponential Least Squares (QCELS) algorithm, our new approach incorporates significant advancements to ensure robust estimation while maintaining a polynomial cost in precision. By leveraging the spectral gap of the Hamiltonian effectively, our algorithm overcomes limitations observed in previous methods like quantum phase estimation (QPE) and robust phase estimation (RPE). Going beyond global depolarizing error channels, our work underscores the significance and practical advantages of utilizing randomized compiling techniques to tailor quantum noise towards depolarizing error channels. Our research demonstrates the feasibility of ground-state energy estimation in the presence of depolarizing noise, offering potential advancements in error correction and algorithmic-level error mitigation for quantum algorithms. △ Less

Submitted 10 March, 2024; v1 submitted 20 July, 2023; originally announced July 2023.

Comments: 35 pages, 8 figures. The first two authors contributed equally to this work

Heisenberg-limited Hamiltonian learning for interacting bosons

Authors: Haoya Li, Yu Tong, Hongkang Ni, Tuvia Gefen, Lexing Ying

Abstract: We develop a protocol for learning a class of interacting bosonic Hamiltonians from dynamics with Heisenberg-limited scaling. For Hamiltonians with an underlying bounded-degree graph structure, we can learn all parameters with root mean squared error $ε$ using $\mathcal{O}(1/ε)$ total evolution time, which is independent of the system size, in a way that is robust against state-preparation and mea… ▽ More We develop a protocol for learning a class of interacting bosonic Hamiltonians from dynamics with Heisenberg-limited scaling. For Hamiltonians with an underlying bounded-degree graph structure, we can learn all parameters with root mean squared error $ε$ using $\mathcal{O}(1/ε)$ total evolution time, which is independent of the system size, in a way that is robust against state-preparation and measurement error. In the protocol, we only use bosonic coherent states, beam splitters, phase shifters, and homodyne measurements, which are easy to implement on many experimental platforms. A key technique we develop is to apply random unitaries to enforce symmetry in the effective Hamiltonian, which may be of independent interest. △ Less

Submitted 10 July, 2023; originally announced July 2023.

Comments: 14 pages with 21-page appendix

Quantum Tunneling in the Surface Diffusion of Single Hydrogen Atoms on Cu(001)

Authors: Xiaofan Yu, Yangwu Tong, Yong Yang

Abstract: The adsorption and diffusion of hydrogen atoms on Cu(001) are studied using first-principles calculations. By taking into account the contribution of zero-point energy (ZPE), the originally identical barriers are shown to be different for H and D, which are respectively calculated to be ~ 158 meV and ~ 139 meV in height. Using the transfer matrix method (TMM), we are able to calculate the accurate… ▽ More The adsorption and diffusion of hydrogen atoms on Cu(001) are studied using first-principles calculations. By taking into account the contribution of zero-point energy (ZPE), the originally identical barriers are shown to be different for H and D, which are respectively calculated to be ~ 158 meV and ~ 139 meV in height. Using the transfer matrix method (TMM), we are able to calculate the accurate probability of transmission across the barriers. The crucial role of quantum tunneling is clearly demonstrated at low-temperature region. By introducing a temperature-dependent attempting frequency prefactor, the rate constants and diffusion coefficients are calculated. The results are in agreement with the experimental measurements at temperatures from ~ 50 K to 80 K. △ Less

Submitted 8 June, 2023; originally announced June 2023.

Comments: 18 pages, 4 figures, 2 tables

Journal ref: Chinese Physics B (2023)

On the complexity of implementing Trotter steps

Authors: Guang Hao Low, Yuan Su, Yu Tong, Minh C. Tran

Abstract: Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner. However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques. We develop methods to perform faster Trotter steps with complexity sublinear in… ▽ More Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner. However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques. We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms. We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law. Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques. We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank. Combining with a tighter error analysis, we show that it suffices to use $\left(η^{1/3}n^{1/3}+\frac{n^{2/3}}{η^{2/3}}\right)n^{1+o(1)}$ gates to simulate uniform electron gas with $n$ spin orbitals and $η$ electrons in second quantization in real space, asymptotically improving over the best previous work. We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation. We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic $n$-qubit $2$-local Hamiltonians with commuting terms require at least $Ω(n^2)$ gates to evolve with accuracy $ε=Ω(1/poly(n))$ for time $t=Ω(ε)$. Our proof is based on a gate-efficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-$2$ subspace, which may be of independent interest. Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity. △ Less

Submitted 11 May, 2023; v1 submitted 16 November, 2022; originally announced November 2022.

Comments: 69 pages, 7 figures. Tightened gate complexity analysis with no amplitude amplification prefactors. Discussed ancilla space complexity. Added master theorem analysis of the recursive low-rank algorithm. Enhanced version of the article published in PRX Quantum at https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.4.020323

Journal ref: PRX Quantum 4, 020323 (2023)

Activated Dissociation of H2 on Cu(001): The Role of Quantum Tunneling

Authors: Xiaofan Yu, Yangwu Tong, Yong Yang

Abstract: The activation and dissociation of H2 molecules on Cu(001) surface is studied theoretically. The activation barrier for the dissociation of H2 on Cu(001) is determined by first-principles calculations to be ~ 0.59 eV in height. Electron transfer from the substrate Cu to H2 plays a key role in the activation, breaking of the H-H bond and the formation of the Cu-H bonds. At around the critical heigh… ▽ More The activation and dissociation of H2 molecules on Cu(001) surface is studied theoretically. The activation barrier for the dissociation of H2 on Cu(001) is determined by first-principles calculations to be ~ 0.59 eV in height. Electron transfer from the substrate Cu to H2 plays a key role in the activation, breaking of the H-H bond and the formation of the Cu-H bonds. At around the critical height of bond breaking, two stationary states are identified, which correspond respectively to the molecular and dissociative state. Using the transfer matrix method, we are able to study the role of quantum tunneling in the dissociation process along the minimum energy pathway (MEP), which is found to be significant at room temperature and below. At given temperatures, the tunneling contributions from the translational and vibrational motions of H2 are quantified for the dissociation process. Within a wide range of temperatures, the effects of quantum tunneling on the effective barriers of dissociation and the rate constants are revealed. The deduced energetic parameters associated with thermal equilibrium and non-equilibrium (molecular beam) conditions are comparable with experimental data. In the low-temperature region, crossover from classical to quantum regime is identified. △ Less

Submitted 2 June, 2023; v1 submitted 11 November, 2022; originally announced November 2022.

Comments: 31 pages, 10 figures

Journal ref: Chinese Physics B (2023)

Learning many-body Hamiltonians with Heisenberg-limited scaling

Authors: Hsin-Yuan Huang, Yu Tong, Di Fang, Yuan Su

Abstract: Learning a many-body Hamiltonian from its dynamics is a fundamental problem in physics. In this work, we propose the first algorithm to achieve the Heisenberg limit for learning an interacting $N$-qubit local Hamiltonian. After a total evolution time of $\mathcal{O}(ε^{-1})$, the proposed algorithm can efficiently estimate any parameter in the $N$-qubit Hamiltonian to $ε$-error with high probabili… ▽ More Learning a many-body Hamiltonian from its dynamics is a fundamental problem in physics. In this work, we propose the first algorithm to achieve the Heisenberg limit for learning an interacting $N$-qubit local Hamiltonian. After a total evolution time of $\mathcal{O}(ε^{-1})$, the proposed algorithm can efficiently estimate any parameter in the $N$-qubit Hamiltonian to $ε$-error with high probability. The proposed algorithm is robust against state preparation and measurement error, does not require eigenstates or thermal states, and only uses $\mathrm{polylog}(ε^{-1})$ experiments. In contrast, the best previous algorithms, such as recent works using gradient-based optimization or polynomial interpolation, require a total evolution time of $\mathcal{O}(ε^{-2})$ and $\mathcal{O}(ε^{-2})$ experiments. Our algorithm uses ideas from quantum simulation to decouple the unknown $N$-qubit Hamiltonian $H$ into noninteracting patches, and learns $H$ using a quantum-enhanced divide-and-conquer approach. We prove a matching lower bound to establish the asymptotic optimality of our algorithm. △ Less

Submitted 6 October, 2022; originally announced October 2022.

Comments: 11 pages, 1 figure + 27-page appendix

Time-marching based quantum solvers for time-dependent linear differential equations

Authors: Di Fang, Lin Lin, Yu Tong

Abstract: The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general linear differential equations, a time-marching based quantum solver can suffer from exponentially vanishing success p… ▽ More The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general linear differential equations, a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) the coefficient matrix $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state. Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations. △ Less

Submitted 15 March, 2023; v1 submitted 14 August, 2022; originally announced August 2022.

Comments: 45 pages, 6 figures

Journal ref: Quantum 7, 955 (2023)

Is there evidence for exponential quantum advantage in quantum chemistry?

Authors: Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, Garnet Kin-Lic Chan

Abstract: The idea to use quantum mechanical devices to simulate other quantum systems is commonly ascribed to Feynman. Since the original suggestion, concrete proposals have appeared for simulating molecular and materials chemistry through quantum computation, as a potential ``killer application''. Indications of potential exponential quantum advantage in artificial tasks have increased interest in this ap… ▽ More The idea to use quantum mechanical devices to simulate other quantum systems is commonly ascribed to Feynman. Since the original suggestion, concrete proposals have appeared for simulating molecular and materials chemistry through quantum computation, as a potential ``killer application''. Indications of potential exponential quantum advantage in artificial tasks have increased interest in this application, thus, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation. We conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for quantum chemistry, it may be prudent to assume exponential speedups are not generically available for this problem. △ Less

Submitted 14 November, 2022; v1 submitted 3 August, 2022; originally announced August 2022.

Journal ref: Nat Commun 14, 1952 (2023)

Efficient Depth Selection for the Implementation of Noisy Quantum Approximate Optimization Algorithm

Authors: Yu Pan, Yifan Tong, Shibei Xue, Guofeng Zhang

Abstract: Noise on near-term quantum devices will inevitably limit the performance of Quantum Approximate Optimization Algorithm (QAOA). One significant consequence is that the performance of QAOA may fail to monotonically improve with depth. In particular, optimal depth can be found at a certain point where the noise effects just outweigh the benefits brought by increasing the depth. In this work, we propo… ▽ More Noise on near-term quantum devices will inevitably limit the performance of Quantum Approximate Optimization Algorithm (QAOA). One significant consequence is that the performance of QAOA may fail to monotonically improve with depth. In particular, optimal depth can be found at a certain point where the noise effects just outweigh the benefits brought by increasing the depth. In this work, we propose to use the model selection algorithm to identify the optimal depth with a few iterations of regularization parameters. Numerical experiments show that the algorithm can efficiently locate the optimal depth under relaxation and dephasing noises. △ Less

Submitted 9 July, 2022; originally announced July 2022.

Comments: Submitted. Comments welcome!

Automatic Depth Optimization for Quantum Approximate Optimization Algorithm

Authors: Yu Pan, Yifan Tong, Yi Yang

Abstract: Quantum Approximate Optimization Algorithm (QAOA) is a hybrid algorithm whose control parameters are classically optimized. In addition to the variational parameters, the right choice of hyperparameter is crucial for improving the performance of any optimization model. Control depth, or the number of variational parameters, is considered as the most important hyperparameter for QAOA. In this paper… ▽ More Quantum Approximate Optimization Algorithm (QAOA) is a hybrid algorithm whose control parameters are classically optimized. In addition to the variational parameters, the right choice of hyperparameter is crucial for improving the performance of any optimization model. Control depth, or the number of variational parameters, is considered as the most important hyperparameter for QAOA. In this paper we investigate the control depth selection with an automatic algorithm based on proximal gradient descent. The performances of the automatic algorithm are demonstrated on 7-node and 10-node Max-Cut problems, which show that the control depth can be significantly reduced during the iteration while achieving an sufficient level of optimization accuracy. With theoretical convergence guarantee, the proposed algorithm can be used as an efficient tool for choosing the appropriate control depth as a replacement of random search or empirical rules. Moreover, the reduction of control depth will induce a significant reduction in the number of quantum gates in circuit, which improves the applicability of QAOA on Noisy Intermediate-scale Quantum (NISQ) devices. △ Less

Submitted 29 June, 2022; originally announced June 2022.

Journal ref: Physical Review A 105, 032433 (2022)

$T_2$-limited dc Quantum Magnetometry via Flux Modulation

Authors: Yijin Xie, Caijin Xie, Yunbin Zhu, Ke Jing, Yu Tong, Xi Qin, Haosen Guan, Chang-Kui Duan, Ya Wang, Xing Rong, Jiangfeng Du

Abstract: High-sensitivity magnetometry is of critical importance to the fields of biomagnetism and geomagnetism. However, the magnetometry for the low-frequency signal detection meets the challenge of sensitivity improvement, due to multiple types of low-frequency noise sources. In particular, for the solid-state spin quantum magnetometry, the sensitivity of low frequency magnetic field has been limited by… ▽ More High-sensitivity magnetometry is of critical importance to the fields of biomagnetism and geomagnetism. However, the magnetometry for the low-frequency signal detection meets the challenge of sensitivity improvement, due to multiple types of low-frequency noise sources. In particular, for the solid-state spin quantum magnetometry, the sensitivity of low frequency magnetic field has been limited by short $T_2^*$. Here, we demonstrate a $T_2$-limited dc quantum magnetometry based on the nitrogen-vacancy centers in diamond. The magnetometry, combining the flux modulation and the spin-echo protocol, promotes the sensitivity from being limited by $T_2^*$ to $T_2$ of orders of magnitude longer. The sensitivity of the dc magnetometry of 32 $\rm pT/Hz^{1/2}$ has been achieved, overwhelmingly improved by 100 folds over the Ramsey-type method result of 4.6 $\rm nT/Hz^{1/2}$. Further enhancement of the sensitivity have been systematically analyzed, although challenging but plenty of room is achievable. Our result sheds light on realization of room temperature dc quantum magnetomerty with femtotesla-sensitivity in the future. △ Less

Submitted 15 April, 2022; originally announced April 2022.

Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices

Authors: Yulong Dong, Lin Lin, Yu Tong

Abstract: Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformati… ▽ More Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformation of unitary matrices with real polynomials (QET-U), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit and no multi-qubit control operations, and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anti-commutation relations and further removes the need of implementing the controlled Hamiltonian evolution. Coupled with Trotter based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model. If we are further allowed to use multi-qubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground state preparation and energy estimating using a constant number of ancilla qubits (no more than 3). △ Less

Submitted 18 October, 2022; v1 submitted 12 April, 2022; originally announced April 2022.

Journal ref: PRX Quantum 3, 040305 (2022)

Entanglement area law for 1D gauge theories and bosonic systems

Authors: Nilin Abrahamsen, Yu Tong, Ning Bao, Yuan Su, Nathan Wiebe

Abstract: We prove an entanglement area law for a class of 1D quantum systems involving infinite-dimensional local Hilbert spaces. This class of quantum systems include bosonic models such as the Hubbard-Holstein model, and both U(1) and SU(2) lattice gauge theories in one spatial dimension. Our proof relies on new results concerning the robustness of the ground state and spectral gap to the truncation of H… ▽ More We prove an entanglement area law for a class of 1D quantum systems involving infinite-dimensional local Hilbert spaces. This class of quantum systems include bosonic models such as the Hubbard-Holstein model, and both U(1) and SU(2) lattice gauge theories in one spatial dimension. Our proof relies on new results concerning the robustness of the ground state and spectral gap to the truncation of Hilbert space, applied within the approximate ground state projector (AGSP) framework from previous work. In establishing this area law, we develop a system-size independent bound on the expectation value of local observables for Hamiltonians without translation symmetry, which may be of separate interest. Our result provides theoretical justification for using tensor network methods to study the ground state properties of quantum systems with infinite local degrees of freedom. △ Less

Submitted 3 November, 2022; v1 submitted 29 March, 2022; originally announced March 2022.

Provably accurate simulation of gauge theories and bosonic systems

Authors: Yu Tong, Victor V. Albert, Jarrod R. McClean, John Preskill, Yuan Su

Abstract: Quantum many-body systems involving bosonic modes or gauge fields have infinite-dimensional local Hilbert spaces which must be truncated to perform simulations of real-time dynamics on classical or quantum computers. To analyze the truncation error, we develop methods for bounding the rate of growth of local quantum numbers such as the occupation number of a mode at a lattice site, or the electric… ▽ More Quantum many-body systems involving bosonic modes or gauge fields have infinite-dimensional local Hilbert spaces which must be truncated to perform simulations of real-time dynamics on classical or quantum computers. To analyze the truncation error, we develop methods for bounding the rate of growth of local quantum numbers such as the occupation number of a mode at a lattice site, or the electric field at a lattice link. Our approach applies to various models of bosons interacting with spins or fermions, and also to both abelian and non-abelian gauge theories. We show that if states in these models are truncated by imposing an upper limit $Λ$ on each local quantum number, and if the initial state has low local quantum numbers, then an error at most $ε$ can be achieved by choosing $Λ$ to scale polylogarithmically with $ε^{-1}$, an exponential improvement over previous bounds based on energy conservation. For the Hubbard-Holstein model, we numerically compute a bound on $Λ$ that achieves accuracy $ε$, obtaining significantly improved estimates in various parameter regimes. We also establish a criterion for truncating the Hamiltonian with a provable guarantee on the accuracy of time evolution. Building on that result, we formulate quantum algorithms for dynamical simulation of lattice gauge theories and of models with bosonic modes; the gate complexity depends almost linearly on spacetime volume in the former case, and almost quadratically on time in the latter case. We establish a lower bound showing that there are systems involving bosons for which this quadratic scaling with time cannot be improved. By applying our result on the truncation error in time evolution, we also prove that spectrally isolated energy eigenstates can be approximated with accuracy $ε$ by truncating local quantum numbers at $Λ=\textrm{polylog}(ε^{-1})$. △ Less

Submitted 20 September, 2022; v1 submitted 13 October, 2021; originally announced October 2021.

Journal ref: Quantum 6, 816 (2022)

Collision-induced spin noise

Authors: Shiming Song, Min Jiang, Yushu Qin, Yu Tong, Wenzhe Zhang, Xi Qin, Ren-Bao Liu, Xinhua Peng

Abstract: Collision phenomena are ubiquitous and of importance in determining the microscopic structures and intermolecular interactions of atoms and molecules. The existing approaches are mostly based on atomic or molecular scatterings, which are hindered by the inconvenience of using ultra-high vacuum and low temperature systems. Here we demonstrate a new spin-noise spectroscopic approach by measuring opt… ▽ More Collision phenomena are ubiquitous and of importance in determining the microscopic structures and intermolecular interactions of atoms and molecules. The existing approaches are mostly based on atomic or molecular scatterings, which are hindered by the inconvenience of using ultra-high vacuum and low temperature systems. Here we demonstrate a new spin-noise spectroscopic approach by measuring optical polarization rotation noise of the probe light, which operates with simple apparatus and ambient conditions. Our approach features tens of gigahertz bandwidth and one part-per-million resolution, outperforming existing spin-noise techniques. Enabled by the new technique, we observe the collision-induced spin noise of alkali atoms, and precisely determine key collision parameters, such as collision diameter, well depth, and dominant interaction type. Our work provides a new tool to study a broad range of collision phenomena under ambient conditions. △ Less

Submitted 10 July, 2021; originally announced July 2021.

Comments: 6 pages, 4 figures

Journal ref: Physical Review Applied. 2022 Jan 4;17(1):L011001

Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers

Authors: Lin Lin, Yu Tong

Abstract: Under suitable assumptions, the quantum phase estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground state energy. However, QPE requires a large number of ancilla qubits and large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer. We pr… ▽ More Under suitable assumptions, the quantum phase estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground state energy. However, QPE requires a large number of ancilla qubits and large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer. We propose an alternative method to estimate the ground state energy of a Hamiltonian with Heisenberg-limited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical post-processing procedure. Besides the ground state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian. △ Less

Submitted 3 February, 2022; v1 submitted 22 February, 2021; originally announced February 2021.

Journal ref: PRX Quantum 3, 010318 (2022)

Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions

Authors: Yu Tong, Dong An, Nathan Wiebe, Lin Lin

Abstract: Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block-encode a matrix inverse through a quantum circuit imple… ▽ More Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block-encode a matrix inverse through a quantum circuit implementing the inversion of eigenvalues via classical arithmetics. We demonstrate the application of preconditioned linear system solvers for computing single-particle Green's functions of quantum many-body systems, which are widely used in quantum physics, chemistry, and materials science. We analyze the complexities in three scenarios: the Hubbard model, the quantum many-body Hamiltonian in the planewave-dual basis, and the Schwinger model. We also provide a method for performing Green's function calculation in second quantization within a fixed particle manifold and note that this approach may be valuable for simulation more broadly. Besides solving linear systems, fast inversion also allows us to develop fast algorithms for computing matrix functions, such as the efficient preparation of Gibbs states. We introduce two efficient approaches for such a task, based on the contour integral formulation and the inverse transform respectively. △ Less

Submitted 28 September, 2021; v1 submitted 30 August, 2020; originally announced August 2020.

Journal ref: Phys. Rev. A 104, 032422 (2021)

Near-optimal ground state preparation

Authors: Lin Lin, Yu Tong

Abstract: Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the… ▽ More Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem. △ Less

Submitted 6 December, 2020; v1 submitted 27 February, 2020; originally announced February 2020.

Journal ref: Quantum 4, 372 (2020)

Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

Authors: Lin Lin, Yu Tong

Abstract: We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear… ▽ More We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal $\mathcal{\widetilde{O}}(dκ\log(1/ε))$ query complexity for a $d$-sparse matrix, where $κ$ is the condition number, and $ε$ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification. △ Less

Submitted 8 November, 2020; v1 submitted 31 October, 2019; originally announced October 2019.

Journal ref: Quantum 4, 361 (2020)

Low-rank representation of tensor network operators with long-range pairwise interactions

Authors: Lin Lin, Yu Tong

Abstract: Tensor network operators, such as the matrix product operator (MPO) and the projected entangled-pair operator (PEPO), can provide efficient representation of certain linear operators in high dimensional spaces. This paper focuses on the efficient representation of tensor network operators with long-range pairwise interactions such as the Coulomb interaction. For MPOs, we find that all existing eff… ▽ More Tensor network operators, such as the matrix product operator (MPO) and the projected entangled-pair operator (PEPO), can provide efficient representation of certain linear operators in high dimensional spaces. This paper focuses on the efficient representation of tensor network operators with long-range pairwise interactions such as the Coulomb interaction. For MPOs, we find that all existing efficient methods exploit a peculiar "upper-triangular low-rank" (UTLR) property, i.e. the upper-triangular part of the matrix can be well approximated by a low-rank matrix, while the matrix itself can be full-rank. This allows us to convert the problem of finding the efficient MPO representation into a matrix completion problem. We develop a modified incremental singular value decomposition method (ISVD) to solve this ill-conditioned matrix completion problem. This algorithm yields equivalent MPO representation to that developed in [Stoudenmire and White, Phys. Rev. Lett. 2017]. In order to efficiently treat more general tensor network operators, we develop another strategy for compressing tensor network operators based on hierarchical low-rank matrix formats, such as the hierarchical off-diagonal low-rank (HODLR) format, and the $\mathcal{H}$-matrix format. Though the pre-constant in the complexity is larger, the advantage of using the hierarchical low-rank matrix format is that it is applicable to both MPOs and PEPOs. For the Coulomb interaction, the operator can be represented by a linear combination of $\mathcal{O}(\log(N)\log(N/ε))$ MPOs/PEPOs, each with a constant bond dimension, where $N$ is the system size and $ε$ is the accuracy of the low-rank truncation. Neither the modified ISVD nor the hierarchical low-rank algorithm assumes that the long-range interaction takes a translation-invariant form. △ Less

Submitted 5 September, 2019; originally announced September 2019.

Fault-Tolerant Quantum Walks

Authors: S. D. Freedman, Y. H. Tong, J. B. Wang

Abstract: Quantum walks are expected to serve important modelling and algorithmic applications in many areas of science and mathematics. Although quantum walks have been successfully implemented physically in recent times, no major efforts have been made to combat the error associated with these physical implementations in a fault-tolerant manner. In this paper, we propose a systematic method to implement f… ▽ More Quantum walks are expected to serve important modelling and algorithmic applications in many areas of science and mathematics. Although quantum walks have been successfully implemented physically in recent times, no major efforts have been made to combat the error associated with these physical implementations in a fault-tolerant manner. In this paper, we propose a systematic method to implement fault-tolerant quantum walks in discrete time on arbitrarily complex graphs, using quantum states encoded with the Steane code and a set of universal fault tolerant matrix operations. △ Less

Submitted 6 August, 2014; originally announced August 2014.

Non-adiabatic Arbitary Geometric Gates in 2-qubit NMR Model

Authors: Yu Tong, Ruibao Tao

Abstract: We study a 2-qubit nuclear spin system for realizing an arbitrary geometric quantum phase gate by means of non-adiabatic operation. A single magnetic pulse with multi harmonic frequencies is applied to manipulate the quantum states of 2-qubit instantly. Using resonant transition approximation, the time dependent Hamiltonian of two nuclear spins can be solved analytically. The time evolution of t… ▽ More We study a 2-qubit nuclear spin system for realizing an arbitrary geometric quantum phase gate by means of non-adiabatic operation. A single magnetic pulse with multi harmonic frequencies is applied to manipulate the quantum states of 2-qubit instantly. Using resonant transition approximation, the time dependent Hamiltonian of two nuclear spins can be solved analytically. The time evolution of the wave function is obtained without adiabatic approximation. The parameters of magnetic pulse, such as the frequency, amplitude, phase of each harmonic part as well as the time duration of the pulse, are determined for achieving an arbitrary non-adiabatic geometric phase gate. The derivation of non-adiabatic geometric controlled phase gates and A-A phase are also addressed. △ Less

Submitted 16 December, 2006; v1 submitted 5 July, 2006; originally announced July 2006.

Comments: 7 pages, 1 figure