Extended Quantum Color Coding

Abstract

The quantum color coding scheme proposed by Korff and Kempe (quant-ph/0405086) is easily extended so that the color coding quantum system is allowed to be entangled with an extra auxiliary quantum system. It is shown that in the extended scheme we need only $\sim 2\sqrt{N}$ quantum colors to order $N$ objects in large $N$ limit, whereas $\sim N/e$ quantum colors are required in the original non-extended version. The maximum success probability has asymptotics expressed by the Tracy-Widom distribution of the largest eigenvalue of a random GUE matrix.

10 pages

References in corpus (1)

• Level-Spacing Distributions and the Airy Kernel

Cited by in corpus (7)

• Applications of coherent classical communication and the Schur transform to quantum information theory
• Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies
• Identification of a reversible quantum gate: assessing the resources
• Fourier Analytic Approach to Quantum Estimation of Group Action
• Unitary-process discrimination with error margin
• A Classical Algorithm for Quantum $\text{SU}(2)$ Schur Sampling
• Quantum Advantage in Identifying the Parity of Permutations with Certainty