Time complexity in preparing metrologically useful quantum states

• URL: http://arxiv.org/abs/2511.14855v1
• Date: Tue, 18 Nov 2025 19:09:33 GMT
• Title: Time complexity in preparing metrologically useful quantum states
• Authors: Carla M. Quispe Flores, Raphael Kaubruegger, Minh C. Tran, Xun Gao, Ana Maria Rey, Zhexuan Gong,
• Abstract summary: We find a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.<n>Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.
• Score: 1.7654096172598859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
  We show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2(1-varepsilon)n)$ for any $varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH)<n>We provide a quantum algorithm that runs in $O(sqrt2n)$ time for an arbitrary $1/mathrmpoly(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Goss
  arXiv  Detail & Related papers  (2026-02-16T01:11:55Z)
• Dirac particles, spin and photons [51.56484100374058]
  We describe relativistic particles with spin as points moving in phase space $X=T* R1,3times C2_Ltimes C2_R$.<n>We show that taking into account the charges $q_sfv=pm 1$ of the fields $Psi_pm$ changes the definitions of the inner products and currents.
  arXiv  Detail & Related papers  (2025-08-29T12:47:56Z)
• Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
  We significantly improve the sample complexity of estimating $operatornametr(rhoq)$ in both the upper and lower bounds.<n>Our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling.
  arXiv  Detail & Related papers  (2025-05-14T17:06:33Z)
• Out-of-equilibrium dynamics across the first-order quantum transitions of one-dimensional quantum Ising models [0.0]
  We study the out-of-equilibrium dynamics of one-dimensional quantum Ising models in a transverse field $g$.<n>We consider nearest-neighbor Ising chains of size $L$ with periodic boundary conditions.
  arXiv  Detail & Related papers  (2025-04-14T20:00:27Z)
• Lieb-Robinson bounds with exponential-in-volume tails [0.0]
  Lieb-Robinson bounds demonstrate the emergence of locality in many-body quantum systems.<n>Perturbation theory and cluster expansion methods suggest that at short times, volume-filling operators are suppressed.<n>We show that disorder operators have volume-law suppression near the "solvable (Ising) point" in quantum phases with spontaneous symmetry breaking.
  arXiv  Detail & Related papers  (2025-02-04T19:00:12Z)
• Optimal convergence rates in trace distance and relative entropy for the quantum central limit theorem [2.7855886538423182]
  We show that for a centered $m$-mode quantum state with finite third-order moments, the trace distance between $rhoboxplus n$ and $rho_G$ decays at the optimal rate of $mathcalO(n-1/2)$.<n>For states with finite fourth-order moments, we prove that the relative entropy between $rhoboxplus n$ and $rho_G$ decays at the optimal rate of $mathcalO(n-1)$.
  arXiv  Detail & Related papers  (2024-10-29T12:35:47Z)
• Quantum connection, charges and virtual particles [65.268245109828]
  A quantum bundle $L_hbar$ is endowed with a connection $A_hbar$ and its sections are standard wave functions $psi$ obeying the Schr"odinger equation. We will lift the bundles $L_Cpm$ and connection $A_hbar$ on them to the relativistic phase space $T*R3,1$ and couple them to the Dirac spinor bundle describing both particles and antiparticles.
  arXiv  Detail & Related papers  (2023-10-10T10:27:09Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model.<n>Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$.<n>Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
  arXiv  Detail & Related papers  (2023-08-16T06:46:37Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians [0.0]
  We present a framework for constructing quantum circuits that implement the multiply-controlled unitary $textSelect(H) equiv sum_ell. $textSelect(H)$ is one of the main subroutines of several quantum algorithms.
  arXiv  Detail & Related papers  (2020-04-08T18:00:04Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.