Tight Bound for Quantum Unitary Time-Reversal

• URL: http://arxiv.org/abs/2507.05736v3
• Date: Fri, 25 Jul 2025 07:20:15 GMT
• Title: Tight Bound for Quantum Unitary Time-Reversal
• Authors: Kean Chen, Nengkun Yu, Zhicheng Zhang,
• Abstract summary: Time-reversal of unitary evolution is fundamental in quantum information processing.<n>Many scenarios assume free access to the time-reverse of an unknown unitary.<n>We provide a tight query lower bound $Omega(epsilon)d2)$ for the unitary time-reversal to within diamond norm error.
• Score: 20.735339332424942
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Time-reversal of unitary evolution is fundamental in quantum information processing. Many scenarios, particularly those in quantum learning and metrology, assume free access to the time-reverse of an unknown unitary. In this paper, we settle the query complexity of the unitary time-reversal task: approximately implementing $U^{-1}$ given only black-box access to an unknown $d$-dimensional unitary $U$. We provide a tight query lower bound $\Omega((1-\epsilon)d^2)$ for the unitary time-reversal to within diamond norm error $\epsilon$. Notably, our lower bound applies to general coherent protocols with unbounded ancillas, and holds even when $\epsilon$ is an average-case distance error and access to control-$U$ is available.

Related papers

• Pauli measurements are not optimal for single-copy tomography [34.83118849281207]
  We prove a stronger upper bound of $O(frac10Nepsilon2)$ and a lower bound of $Omega(frac9.118Nepsilon2)$.<n>This demonstrates the first known separation between Pauli measurements and structured POVMs.
  arXiv  Detail & Related papers  (2025-02-25T13:03:45Z)
• 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)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Time-of-arrival distributions for continuous quantum systems and application to quantum backflow [0.0]
  We show that for any continuous quantum system (Gaussian or otherwise) the time-of-arrival problem is hidden within the Born rule. This finding suggests that the answer to the long-lasting time-of-arrival problem is in fact secretly hidden within the Born rule.
  arXiv  Detail & Related papers  (2024-05-03T11:33:52Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD.<n>Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers.<n>Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
  We show that a phase estimation algorithm with precision $delta$ and error probability $epsilon$ has cost $Omegaleft(frac1deltalog1epsilonright)$. We also show that having lots advice (applications of the advice-preparing unitary) does not significantly reduce cost, and neither does knowledge of the eigenbasis of $U$.
  arXiv  Detail & Related papers  (2023-05-08T17:46:01Z)
• $TimeEvolver$: A Program for Time Evolution With Improved Error Bound [0.0]
  We present $TimeEvolver$, a program for computing time evolution in a generic quantum system. It relies on Krylov subspace techniques to tackle the problem of multiplying the exponential of a large sparse matrix $i H$. The fact that $H$ is Hermitian makes it possible to provide an easily computable bound on the accuracy of the Krylov approximation.
  arXiv  Detail & Related papers  (2022-05-30T18:00:16Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  We develop a novel connection between discrepancy minimization and (quantum) communication complexity. We show that for every collection of symmetric $n times n$ $A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ there exist signs $x in pm 1n such that the maximum eigenvalue of $sum_i leq n x_i A_i$ is at most
  arXiv  Detail & Related papers  (2021-10-19T16:51:11Z)
• Complexity of quantum state verification in the quantum linear systems problem [0.12891210250935145]
  We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A vec x = vec b$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=Omega(kappa)$.
  arXiv  Detail & Related papers  (2020-07-30T19:20:49Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• 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.