Sandwich test for Quantum Phase Estimation

• URL: http://arxiv.org/abs/2507.23716v2
• Date: Sun, 03 Aug 2025 09:18:55 GMT
• Title: Sandwich test for Quantum Phase Estimation
• Authors: Avatar Tulsi,
• Abstract summary: Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications.<n>Many QPE algorithms use the Hadamard test to estimate $langle psi|Uk|psirangle$ for a large integer $k$.<n>We present a new algorithm, the SANDWICH test to address this bottleneck.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum Phase Estimation (QPE) has potential for a scientific revolution through numerous practical applications like finding better medicines, batteries, materials, catalysts etc. Many QPE algorithms use the Hadamard test to estimate $\langle \psi|U^{k}|\psi\rangle$ for a large integer $k$ for an efficiently preparable initial state $|\psi\rangle$ and an efficiently implementable unitary operator $U$. The Hadamard test is hard to implement because it requires controlled applications of $U^{k}$. Recently, a Sequential Hadamard test (SHT) was proposed (arXiv:2506.18765) which requires controlled application of $U$ only but its total run time $T_{\rm tot}$ scales as $\mathcal{O}(k^{3}/\epsilon^{2}r_{\rm min}^{2})$ where $r_{\rm min}$ is the minimum value of $|\langle \psi|U^{k'}|\psi\rangle|$ among all integers $k' \leq k$. Typically $r_{\rm min}$ is exponentially low and SHT becomes too slow. We present a new algorithm, the SANDWICH test to address this bottleneck. Our algorithm uses efficient preparation of the initial state $|\psi\rangle$ to efficiently implement the SPROTIS operator $R_{\psi}^{\phi}$ where SPROTIS stands for the Selective Phase Rotation of the Initial State. It sandwiches the SPROTIS operator between $U^{a}$ and $U^{b}$ for integers $\{a,b\} \leq k$ to estimate $\langle \psi|U^{k}|\psi\rangle$. The total run time $T_{\rm tot}$ is $\mathcal{O}(k^{2}\ln k/ \epsilon^{2} s_{\rm min}^{6})$. Here $s_{\rm min}$ is the minimum value of $|\langle \psi|U^{\hat{k}}|\psi\rangle$ among all integers $\hat{k}$ which are values of the nodes of a random binary sum tree whose root node value is $k$ and leaf nodes' values are $1$ or $0$. It can be reasonably expected that $s_{\rm min} \not\ll 1$ in typical cases because there is wide freedom in choosing the random binary sum tree.

Related papers

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Faster Stochastic Algorithms for Minimax Optimization under Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
  We propose SPIDER-GDA for solving the finite-sum problem of the form $min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$. We prove SPIDER-GDA could find an $epsilon$-optimal solution within $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon)
  arXiv  Detail & Related papers  (2023-07-29T02:26:31Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  Existing optimal first-order methods require $mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$ of computations of both $nabla_x f(x,y)$ and $nabla_y f(x,y)$. We propose a new algorithm that only requires $mathcalO(sqrtkappa_x log 1/epsilon)$ of computations of $nabla_x f(x,
  arXiv  Detail & Related papers  (2022-12-29T19:26:12Z)
• Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
  We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. We prove that $omega(log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states.
  arXiv  Detail & Related papers  (2022-09-29T03:34:03Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  We revisit heavy-tailed corrupted least-squares linear regression assuming to have a corrupted $n$-sized label-feature sample of at most $epsilon n$ arbitrary outliers. We propose a near-optimal computationally tractable estimator, based on the power method, assuming no knowledge on $(Sigma,Xi) nor the operator norm of $Xi$.
  arXiv  Detail & Related papers  (2022-09-06T23:37:31Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
  A stream of integers in $[N]:=1,cdots,N$ is received from a sensor. The goal is to approximate the $n$ points received so far in $P$ by a single frequency. We prove that emphevery set $P$ of $n$ has a weighted subset $Ssubseteq P$.
  arXiv  Detail & Related papers  (2022-03-06T17:07:56Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
  We study the computational complexity of computing the normalizing constant. We show that $sum_Sdet(bf A_S,S)p$ exactly for every (fixed) positive even integer $p$ is UP-hard and Mod$_3$P-hard.
  arXiv  Detail & Related papers  (2021-11-28T14:08:25Z)
• Improved quantum data analysis [1.8416014644193066]
  We give a quantum "Threshold Search" algorithm that requires only $O(log2 m)/epsilon2)$ samples of a $d$-dimensional state. We also give an alternative Hypothesis Selection method using $tildeO((log3 m)/epsilon2)$ samples.
  arXiv  Detail & Related papers  (2020-11-22T01:22:37Z)
• 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)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.