Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.14855

Time complexity in preparing metrologically useful quantum states

Carla M. Quispe Flores, Raphael Kaubruegger, Minh C. Tran, Xun Gao, Ana Maria Rey, Zhexuan Gong

quant-phSubmitted Nov 18, 2025• Announced Nov 20, 2025• 3 citations
arXivHTMLPDF

Abstract

We investigate the fundamental time complexity, as constrained by Lieb-Robinson bounds, for preparing entangled states useful in quantum metrology. We relate the minimum time to the Quantum Fisher Information ($F_Q$) for a system of $N$ quantum spins on a $d$-dimensional lattice with $1/r^α$ interactions with $r$ being the distance between two interacting spins. We focus on states with $F_Q \sim N^{1+γ}$ where $γ\in (0,1]$, i.e., scaling from the standard quantum limit to the Heisenberg limit. For short-range interactions ($α> 2d+1$), we prove the minimum time $t$ scales as $t \gtrsim L^γ$, where $L \sim N^{1/d}$. For long-range interactions, we find a hierarchy of possible speedups: $t \gtrsim L^{γ(α-2d)}$ for $2d < α< 2d+1$, $t \gtrsim \log L$ for $(2-γ)d < α< 2d$, and $t$ may even vanish algebraically in $1/L$ for $α< (2-γ)d$. These bounds extend to the minimum circuit depth required for state preparation, assuming two-qubit gate speeds scale as $1/r^α$. We further show that these bounds are saturable, up to sub-polynomial corrections, for all $α$ at the Heisenberg limit ($γ=1$) and for $α> (2-γ)d$ when $γ<1$. Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.

Comments
9 pages, 2 figures

Related papers

Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation

Zheyu Shen, Yusen Wu, Penghui Yao +2 more

Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $ε$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/ε))$ and gate count $O(nT\log(nT/ε))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $ε$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $Ω(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.

quant-pharXiv:2610.01839•Oct 2, 2026•0 citations

Strong Quantum Metrological Limit from Many-Body Physics

Yaoming Chu, Xiangbei Li, Jianming Cai

Surpassing the standard quantum limit and even reaching the Heisenberg limit using quantum entanglement, represents the Holy Grail of quantum metrology. However, quantum entanglement is a valuable resource that does not come without a price. The exceptional time overhead for the preparation of large-scale entangled states raises disconcerting concerns about whether the Heisenberg limit is fundamentally achievable. Here, we find a universal speed limit set by the Lieb-Robinson light cone for the quantum Fisher information growth to characterize the metrological potential of quantum resource states during their preparation. Our main result establishes a strong precision limit of quantum metrology accounting for the complexity of many-body quantum resource state preparation and reveals a fundamental constraint for reaching the Heisenberg limit in a generic many-body lattice system with bounded one-site energy. It enables us to identify the essential features of quantum many-body systems that are crucial for achieving the quantum advantage of quantum metrology, and brings an interesting connection between many-body quantum dynamics and quantum metrology.

arXiv:2301.12113•Physical Review Letters•Apr 27, 2023•50 citations

Locality and error correction in quantum dynamics with measurement

Aaron J. Friedman, Chao Nan Yin, Yifan Hong +1 more

The speed of light $c$ sets a strict upper bound on the speed of information transfer in both classical and quantum systems. In nonrelativistic quantum systems, the Lieb-Robinson Theorem imposes an emergent speed limit $v \hspace{-0.2mm} \ll \hspace{-0.2mm} c$, establishing locality under unitary evolution and constraining the time needed to perform useful quantum tasks. We extend the Lieb-Robinson Theorem to quantum dynamics with measurements. In contrast to the expectation that measurements can arbitrarily violate spatial locality, we find at most an $(M \hspace{-0.5mm} +\hspace{-0.5mm} 1)$-fold enhancement to the speed $v$ of quantum information, provided the outcomes of measurements in $M$ local regions are known. This holds even when classical communication is instantaneous, and extends beyond projective measurements to weak measurements and other nonunitary channels. Our bound is asymptotically optimal, and saturated by existing measurement-based protocols. We tightly constrain the resource requirements for quantum computation, error correction, teleportation, and generating entangled resource states (Bell, GHZ, quantum-critical, Dicke, W, and spin-squeezed states) from short-range-entangled initial states. Our results impose limits on the use of measurements and active feedback to speed up quantum information processing, resolve fundamental questions about the nature of measurements in quantum dynamics, and constrain the scalability of a wide range of proposed quantum technologies.

arXiv:2206.09929•Jun 20, 2022•43 citations

Signaling and scrambling with strongly long-range interactions

Andrew Y. Guo, Minh C. Tran, Andrew M. Childs +2 more

Strongly long-range interacting quantum systems---those with interactions decaying as a power law $1/{r}^{\ensuremath{\alpha}}$ in the distance $r$ on a $D$-dimensional lattice for $\ensuremath{\alpha}\ensuremath{\le}D$---have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum-information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. In a step towards rectifying this problem, we prove two Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for $\ensuremath{\alpha}\ensuremath{\le}D/2$. Our second bound pertains to generic long-range interacting spin Hamiltonians and gives a tight lower bound for the signaling time to extensive subsets of the system for all $\ensuremath{\alpha}<D$. This many-site signaling time lower bounds the scrambling time in strongly long-range interacting systems.

arXiv:1906.02662•Physical Review A•Jul 8, 2020•55 citations

Enhancing Quantum Metrology by Quantum Resonance Dynamics

Zhixing Zou, Jiangbin Gong, Weitao Chen

Quantum effects in metrology can in principle enhance measurement precision from the so-called standard quantum limit to the Heisenberg limit. Further advancements in quantum metrology largely rely on innovative metrology protocols that can avoid a number of known obstacles, including the challenge of preparing entangled states with sufficient fidelity, the readout noise in measuring highly entangled states, and no-go theorems for quantum metrology under noisy environments. In this Letter, exploiting some peculiar but experimentally feasible dynamical features of a collection of spins with all-to-all time-periodic interactions, we propose a metrology protocol that can circumvent all three mentioned obstacles and yet still make good use of time as a resource for metrology. Specifically, by mapping the dynamics of such a periodically driven spin system to that of a paradigm of quantum chaos but tuned to some high-order quantum resonance, it is shown that a simple SU(2) coherent state can, after evolving to highly entangled states in the ensuing dynamics, be dynamically brought back to the same initial coherent state. The associated quantum Fisher information is found to exhibit quadratic scaling with both the number of spins and the duration of the metrology protocol. The achieved Heisenberg scaling can also largely survive in the presence of Markovian noise. Representing a previously unknown strategy for quantum metrology, the protocol proposed here can be tested on available experimental platforms.

arXiv:2502.01462•Physical Review Letters•May 28, 2025•8 citations

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians

Jeongwan Haah, Matthew B. Hastings, Robin Kothari +1 more

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using ${\mathcal O}( nT {polylog} (nT/\epsilon))$ gates with depth ${\mathcal O}(T { polylog} (nT/\epsilon))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires ${\widetilde{\Omega}}(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb--Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.

arXiv:1801.03922•SIAM Journal on Computing•Jan 12, 2021•226 citations
We investigate the fundamental time complexity, as constrained by Lieb-Robinson bounds, for preparing entangled states useful in quantum metrology. We relate the minimum time to the Quantum Fisher Information (FQF_QFQ​) for a system of NNN quantum spins on a ddd-dimensional lattice with 1/rα1/r^α1/rα interactions with rrr being the distance between two interacting spins. We focus on states with FQ∼N1+γF_Q \sim N^{1+γ}FQ​∼N1+γ where γ∈(0,1]γ\in (0,1]γ∈(0,1], i.e., scaling from the standard quantum limit to the Heisenberg limit. For short-range interactions (α>2d+1α> 2d+1α>2d+1), we prove the minimum time ttt scales as t≳Lγt \gtrsim L^γt≳Lγ, where L∼N1/dL \sim N^{1/d}L∼N1/d. For long-range interactions, we find a hierarchy of possible speedups: t≳Lγ(α−2d)t \gtrsim L^{γ(α-2d)}t≳Lγ(α−2d) for 2d<α<2d+12d < α< 2d+12d<α<2d+1, t≳log⁡Lt \gtrsim \log Lt≳logL for (2−γ)d<α<2d(2-γ)d < α< 2d(2−γ)d<α<2d, and ttt may even vanish algebraically in 1/L1/L1/L for α<(2−γ)dα< (2-γ)dα<(2−γ)d. These bounds extend to the minimum circuit depth required for state preparation, assuming two-qubit gate speeds scale as 1/rα1/r^α1/rα. We further show that these bounds are saturable, up to sub-polynomial corrections, for all ααα at the Heisenberg limit (γ=1γ=1γ=1) and for α>(2−γ)dα> (2-γ)dα>(2−γ)d when γ<1γ<1γ<1. Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy εεε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an nnn-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1T\ge1T≥1, with circuit depth O(Tlog⁡(nT/ε))O(T\log(nT/ε))O(Tlog(nT/ε)) and gate count O(nTlog⁡(nT/ε))O(nT\log(nT/ε))O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time TTT in the stated regime and sufficiently small fixed error εεε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). This matches our O(log⁡n)O(\log n)O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
Surpassing the standard quantum limit and even reaching the Heisenberg limit using quantum entanglement, represents the Holy Grail of quantum metrology. However, quantum entanglement is a valuable resource that does not come without a price. The exceptional time overhead for the preparation of large-scale entangled states raises disconcerting concerns about whether the Heisenberg limit is fundamentally achievable. Here, we find a universal speed limit set by the Lieb-Robinson light cone for the quantum Fisher information growth to characterize the metrological potential of quantum resource states during their preparation. Our main result establishes a strong precision limit of quantum metrology accounting for the complexity of many-body quantum resource state preparation and reveals a fundamental constraint for reaching the Heisenberg limit in a generic many-body lattice system with bounded one-site energy. It enables us to identify the essential features of quantum many-body systems that are crucial for achieving the quantum advantage of quantum metrology, and brings an interesting connection between many-body quantum dynamics and quantum metrology.
The speed of light ccc sets a strict upper bound on the speed of information transfer in both classical and quantum systems. In nonrelativistic quantum systems, the Lieb-Robinson Theorem imposes an emergent speed limit v≪cv \hspace{-0.2mm} \ll \hspace{-0.2mm} cv≪c, establishing locality under unitary evolution and constraining the time needed to perform useful quantum tasks. We extend the Lieb-Robinson Theorem to quantum dynamics with measurements. In contrast to the expectation that measurements can arbitrarily violate spatial locality, we find at most an (M+1)(M \hspace{-0.5mm} +\hspace{-0.5mm} 1)(M+1)-fold enhancement to the speed vvv of quantum information, provided the outcomes of measurements in MMM local regions are known. This holds even when classical communication is instantaneous, and extends beyond projective measurements to weak measurements and other nonunitary channels. Our bound is asymptotically optimal, and saturated by existing measurement-based protocols. We tightly constrain the resource requirements for quantum computation, error correction, teleportation, and generating entangled resource states (Bell, GHZ, quantum-critical, Dicke, W, and spin-squeezed states) from short-range-entangled initial states. Our results impose limits on the use of measurements and active feedback to speed up quantum information processing, resolve fundamental questions about the nature of measurements in quantum dynamics, and constrain the scalability of a wide range of proposed quantum technologies.
Strongly long-range interacting quantum systems---those with interactions decaying as a power law $1/{r}^{\ensuremath{\alpha}}$ in the distance rrr on a DDD-dimensional lattice for $\ensuremath{\alpha}\ensuremath{\le}D$---have received significant interest in recent years. They are present in leading experimental platforms for quantum computation and simulation, as well as in theoretical models of quantum-information scrambling and fast entanglement creation. Since no notion of locality is expected in such systems, a general understanding of their dynamics is lacking. In a step towards rectifying this problem, we prove two Lieb-Robinson-type bounds that constrain the time for signaling and scrambling in strongly long-range interacting systems, for which no tight bounds were previously known. Our first bound applies to systems mappable to free-particle Hamiltonians with long-range hopping, and is saturable for $\ensuremath{\alpha}\ensuremath{\le}D/2$. Our second bound pertains to generic long-range interacting spin Hamiltonians and gives a tight lower bound for the signaling time to extensive subsets of the system for all $\ensuremath{\alpha}<D$. This many-site signaling time lower bounds the scrambling time in strongly long-range interacting systems.
Quantum effects in metrology can in principle enhance measurement precision from the so-called standard quantum limit to the Heisenberg limit. Further advancements in quantum metrology largely rely on innovative metrology protocols that can avoid a number of known obstacles, including the challenge of preparing entangled states with sufficient fidelity, the readout noise in measuring highly entangled states, and no-go theorems for quantum metrology under noisy environments. In this Letter, exploiting some peculiar but experimentally feasible dynamical features of a collection of spins with all-to-all time-periodic interactions, we propose a metrology protocol that can circumvent all three mentioned obstacles and yet still make good use of time as a resource for metrology. Specifically, by mapping the dynamics of such a periodically driven spin system to that of a paradigm of quantum chaos but tuned to some high-order quantum resonance, it is shown that a simple SU(2) coherent state can, after evolving to highly entangled states in the ensuing dynamics, be dynamically brought back to the same initial coherent state. The associated quantum Fisher information is found to exhibit quadratic scaling with both the number of spins and the duration of the metrology protocol. The achieved Heisenberg scaling can also largely survive in the presence of Markovian noise. Representing a previously unknown strategy for quantum metrology, the protocol proposed here can be tested on available experimental platforms.
We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on nnn qubits for time TTT up to error ϵ\epsilonϵ using O(nTpolylog(nT/ϵ)){\mathcal O}( nT {polylog} (nT/\epsilon))O(nTpolylog(nT/ϵ)) gates with depth O(Tpolylog(nT/ϵ)){\mathcal O}(T { polylog} (nT/\epsilon))O(Tpolylog(nT/ϵ)). Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in nTnTnT and polylogarithmic in 1/ϵ1/\epsilon1/ϵ. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires Ω~(nT){\widetilde{\Omega}}(nT)Ω(nT) gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To the best of our knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb--Robinson bounds. In the appendix, we prove a Lieb--Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb--Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting.