Query complexity of unitary operation discrimination

• URL: http://arxiv.org/abs/2012.02944v2
• Date: Tue, 22 Nov 2022 09:23:02 GMT
• Title: Query complexity of unitary operation discrimination
• Authors: Xiaowei Huang and Lvzhou Li
• Abstract summary: Discrimination of unitary operations is fundamental in quantum computation and information. We show how many queries are required for achieving a desired failure probability $epsilon$ of discrimination between $U$ and $V$.
• Score: 6.6802048869908965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Discrimination of unitary operations is fundamental in quantum computation and information. A lot of quantum algorithms including the well-known Deutsch-Jozsa algorithm, Simon's algorithm, and Grover's algorithm can essentially be regarded as discriminating among individual, or sets of unitary operations (oracle operators). The problem of discriminating between two unitary operations $U$ and $V$ can be described as: Given $X\in\{U, V\}$, determine which one $X$ is. If $X$ is given with multiple copies, then one can design an adaptive procedure that takes multiple queries to $X$ to output the identification result of $X$. In this paper, we consider the problem: How many queries are required for achieving a desired failure probability $\epsilon$ of discrimination between $U$ and $V$. We prove in a uniform framework: (i) if $U$ and $V$ are discriminated with bound error $\epsilon$ , then the number of queries $T$ must satisfy $T\geq \left\lceil\frac{2\sqrt{1-4\epsilon(1-\epsilon)}}{\Theta (U^\dagger V)}\right\rceil$, and (ii) if they are discriminated with one-sided error $\epsilon$, then there is $T\geq \left\lceil\frac{2\sqrt{1-\epsilon^2}}{\Theta (U^\dagger V)}\right\rceil$, where $\lceil k\rceil$ denotes the minimum integer not less than $k$ and $\Theta(W)$ denotes the length of the smallest arc containing all the eigenvalues of $W$ on the unit circle.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Differentially Private Approximate Pattern Matching [0.0]
  We consider the $k$-approximate pattern matching problem under differential privacy. The goal is to report or count allimate variants of a given string $S$ which have a Hamming distance at most $k$ to a pattern $P$. We give 1) an $epsilon$-differentially private algorithm with an additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) an $epsilon$-differentially private algorithm with an additive error $O(epsilon-1
  arXiv  Detail & Related papers  (2023-11-13T15:53:45Z)
• 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)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  We give an algorithm for this task that achieves an expected $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$ holds not only in expectation but always.
  arXiv  Detail & Related papers  (2020-12-16T17:58:45Z)
• 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)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  We give an algorithm for identifying a $k$-mixture using samples of $m=2k$ iid binary random variables. It suffices to know the moments to additive accuracy $w_mincdotzetaO(k)$.
  arXiv  Detail & Related papers  (2020-07-16T04:23:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• 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)

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.