The Efficiency of Quantum Identity Testing of Multiple States

Preprint English OPEN
Kada, Masaru ; Nishimura, Harumichi ; Yamakami, Tomoyuki (2008)

We examine two quantum operations, the Permutation Test and the Circle Test, which test the identity of n quantum states. These operations naturally extend the well-studied Swap Test on two quantum states. We first show the optimality of the Permutation Test for any input size n as well as the optimality of the Circle Test for three input states. In particular, when n=3, we present a semi-classical protocol, incorporated with the Swap Test, which approximates the Circle Test efficiently. Furthermore, we show that, with help of classical preprocessing, a single use of the Circle Test can approximate the Permutation Test efficiently for an arbitrary input size n.
  • References (15)
    15 references, page 1 of 2

    [1] D. Aharonov, A. Kitaev and N. Nisan. Quantum circuits with mixed states. Proc. 30th STOC, pp.20-30, 1998.

    [2] A. Ambainis. Communication complexity in a 3-computer model. Algorithmica 16(3) (1996) 298-301.

    [3] A. Ambainis and Y. Shi. Distributed construction of quantum fingerprints. Quantum Information and Computation 4(2) (2004) 146-151.

    [4] L. Babai and P.G. Kimmel. Randomized simultaneous messages: Solution of a problem of Yao in communication complexity. Proc. 12th CCC, pp.239-246, 1997.

    [5] A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa and C. Macchiavello. Stabilization of quantum computations by symmetrization. SIAM J. Comput. 26(5) (1997) 1541-1557.

    [6] J. Niel de Beaudrap. One-qubit fingerprinting schemes. Phys. Rev. A 69 (2004) Article no. 022307.

    [7] H. Buhrman, R. Cleve, J. Watrous and R. de Wolf. Quantum fingerprinting. Phys. Rev. Lett. 87 (2001) Article no. 167902.

    [8] J. Du, P. Zou, X. Peng, D. K. L. Oi, L. C. Kwek, C. H. Oh and A. Ekert. Experimental quantum multimeter and one-qubit fingerprinting. Phys. Rev. A 74 (2006) Article no. 042319.

    [9] A.K. Ekert, C.M. Alves, D.K.L. Oi, M. Horodecki, P. Horodecki and L.C. Kwek. Direct estimations of linear and non-linear functionals of a quantum state. Phys. Rev. Lett. 88 (2002) Article no. 217901.

    [10] K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation and orbit coset in quantum computing. Proc. 35th STOC, pp.1-9, 2003.

  • Metrics
    No metrics available
Share - Bookmark