Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuery complexity of unitary operation discrimination
162
0
0.0
(
0
)
Authors
Lvzhou Li
Ask ChatGPT about the research
No Arabic 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 algorithm, and Grover 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 $Xin{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 $Tgeq leftlceilfrac{2sqrt{1-4epsilon(1-epsilon)}}{Theta (U^dagger V)}rightrceil$, and (ii) if they are discriminated with one-sided error $epsilon$, then there is $Tgeq leftlceilfrac{2sqrt{1-epsilon}}{Theta (U^dagger V)}rightrceil$, where $Theta(W)$ denotes the length of the smallest arc containing all the eigenvalues of $W$ on the unit circle.
rate research
Read More
We provide a description of the problem of the discrimination of two quantum states in terms of receiver operation characteristics analysis, a prevalent approach in classical statistics. Receiveroperation characteristics diagrams provide an expressive representation of the problem, in which quantities such as the fidelity and the trace distance also appear explicitly. In addition we introduce an alternative quantum generalization of the classical Bhattacharyya coefficient. We evaluate our quantum Bhattacharyya coefficient for certain situations and describe some of its properties. These properties make it applicable as another possible quantifier of the similarity of quantum states.
We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for functions with range {0,1}. These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.
We combine the classical notions and techniques for bounded query classes with those developed in quantum computing. We give strong evidence that quantum queries to an oracle in the class NP does indeed reduce the query complexity of decision problems. Under traditional complexity assumptions, we obtain an exponential speedup between the quantum and the classical query complexity of function classes. For decision problems and function classes we obtain the following results: o P_||^NP[2k] is included in EQP_||^NP[k] o P_||^NP[2^(k+1)-2] is included in EQP^NP[k] o FP_||^NP[2^(k+1)-2] is included in FEQP^NP[2k] o FP_||^NP is included in FEQP^NP[O(log n)] For sets A that are many-one complete for PSPACE or EXP we show that FP^A is included in FEQP^A[1]. Sets A that are many-one complete for PP have the property that FP_||^A is included in FEQP^A[1]. In general we prove that for any set A there is a set X such that FP^A is included in FEQP^X[1], establishing that no set is superterse in the quantum setting.
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
We present three new quantum algorithms in the quantum query model for textsc{graph-collision} problem: begin{itemize} item an algorithm based on tree decomposition that uses $Oleft(sqrt{n}t^{sfrac{1}{6}}right)$ queries where $t$ is the treewidth of the graph; item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(sqrt{n}+sqrt{alpha^{**}})$ queries, where $alpha^{**}(G)$ is a graph parameter defined by [alpha^{**}(G):=min_{VCtext{-- vertex cover of}G}{max_{substack{Isubseteq VCItext{-- independent set}}}{sum_{vin I}{deg{v}}}};] item an algorithm for a subclass of circulant graphs that uses $O(sqrt{n})$ queries. end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(sqrt{n} log^c n)$ queries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
