Query complexity of unitary operation discrimination

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\ge \lceil \frac{2\sqrt{1-4\epsilon (1-\epsilon )}}{\Theta (U^{†}V)}\rceil$, and (ii) if they are discriminated with one-sided error $\epsilon$, then there is $T\ge \lceil \frac{2\sqrt{1-{\epsilon }^2}}{\Theta (U^{†}V)}\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.

arXiv commentarXiv admin note: text overlap with arXiv:1711.03865

References in corpus (16)

• Statistical distinguishability between unitary operations
• Using entanglement improves precision of quantum measurements
• Optimal discrimination of quantum operations
• The Perfect Distinguishability of Quantum Operations
• Unambiguous discrimination among quantum operations
• Local Distinguishability of Multipartite Unitary Operations
• Identification and Distance Measures of Measurement Apparatus
• Unambiguous discrimination among oracle operators
• Minimax discrimination of two Pauli channels
• Unitary transformations can be identified locally
• Local Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations Acting on Two-Qudits by LOCC
• Discrimination of two-qubit unitaries via local operations and classical communication
• Optimal discrimination between quantum operations
• Identification of a reversible quantum gate: assessing the resources
• Capability of local operations and classical communication for distinguishing bipartite unitary operations
• Sequential scheme for locally discriminating bipartite unitary operations without inverses

Cited by in corpus (3)

• Limitation of maximally entangled probes for single-shot distinguishability of unitaries
• Quantum Wasserstein distance between unitary operations
• Single-shot antidistinguishability of unitary operations