Quantum Testers for Hidden Group Properties

• Autorzy: Friedl K. , Santha M. , Magniez F. , Sen P.
• Języki publikacji: EN

Abstrakty

EN

We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for their testing problem in the classical model of computing. These are periodicity in groups and the common coset range property of two functions having identical ranges within each coset of some normal subgroup. Our periodicity tester is efficient in Abelian groups and generalizes, in several aspects, previous periodicity testers. This is achieved by introducing a technique refining the majority correction process widely used for proving robustness of algebraic properties. The periodicity tester in non-Abelian groups and the common coset range tester are query efficient.

Słowa kluczowe

EN

quantum computing; property testing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 325--340
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Friedl K.

autor

Santha M.

autor

Magniez F.

autor

Sen P.

• LRI, Univ Paris-Sud, CNRS F-91405 Orsay, France,

Bibliografia

• [1] D. Aharonov. Quantum computation - A review. In Annual Review of Computational Physics, volume VI. World Scientific, 1998.
• [2] C. H. Bennett and G. Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proc. IEEE International Conference on Computers, Systems, and Signal Processing, pages 175-179, 1984.
• [3] H. Buhrman, L. Fortnow, I. Newman, and H. Rőhrig. Quantum property testing. In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 480-488, 2003.
• [4] M. Blum and S. Kannan. Designing programs that check their work. J. ACM, 42(1):269-291, 1995.
• [5] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549-595, 1993.
• [6] W. van Dam, F. Magniez, M. Mosca, and M. Santha. Self-testing of universal and fault-tolerant sets of quantum gates. SIAM Journal of Computing, Vol. 37, No. 2, pp. 611-629, 2007.
• [7] M. Ettinger and P. Høyer. On quantum algorithms for noncommutative hidden subgroups. Adv. in Appl. Math., 25(3):239-251, 2000.
• [8] E. Fischer. The art of uninformed decisions: A primer to property testing, the computational complexity. In The Computational Complexity Column, Bulletin of the EATCS, volume 75, pp. 97-126, 2001.
• [9] K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation and orbit coset in quantum computing. In Proc. 35th ACM STOC, pages 1-9, 2003.
• [10] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998.
• [11] O. Goldreich. Combinatorial property testing - A survey. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1998.
• [12] O. Goldreich and D. Ron. Property testing in bounded degree graphs. In Proc. 27th ACM STOC, pages 406-415, 1997.
• [13] M. Grigni, L. Schulman, M. Vazirani, and U. Vazirani. Quantum mechanical algorithms for the nonabelian hidden subgroup problem. In Proc. 33rd ACM STOC, pages 68-74, 2001.
• [14] L. Hales. The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem. PhD thesis, University of California, Berkeley, 2002.
• [15] L. Hales and S. Hallgren. An improved quantum Fourier transform algorithm and applications. In Proc. 41st IEEE FOCS, pages 515-525, 2000.
• [16] S. Hallgren, A. Russell, and A. Ta-Shma. Normal subgroup reconstruction and quantum computation using group representations. SIAM J. Comp., 32(4): 916-934, 2003.
• [17] A. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. Technical report no. 9511026, Quantum Physics e-Print archive, 1995.
• [18] M. Kiwi, F. Magniez, and M. Santha. Exact and approximate testing/correcting of algebraic functions: A survey. In Proc. 1st SOTACS, volume 2292, pages 30-83. LNCS, 2000.
• [19] D. Mayers and A. Yao. Quantum cryptography with imperfect apparatus. In Proc. 39th IEEE FOCS, pages 503-509, 1998.
• [20] F. Magniez, D. Mayers, M. Mosca, and H. Ollivier. Self-testing of quantum circuits. In Proc. 33rd ICALP, volume 4051 of Lecture Notes in Computer Science, pages 72-83. Verlag, 2006.
• [21] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
• [22] J. Preskill. Quantum information and computation. http://www.theory.caltech.edu/~people/preskill/ph229/, 1998.
• [23] D. Ron. Property testing (a tutorial). In Handbook on Randomization, Kluwer Press, 2001.
• [24] E. G. Rieffel and W. Polak. An introduction to quantum computing for non-physicists. ACM Computing Surveys, 32(3):300-335, 2000.
• [25] R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comp., 25(2):23-32, 1996.
• [26] R. Rubinfeld. On the robustness of functional equations. SIAM J. Comp., 28(6):1972-1997, 1999.
• [27] J.-P. Serre. Linear representations of finite groups. In Graduate Texts in Mathematics, volume 42. Springer-Verlag, 1977.
• [28] P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer SIAM J. Comp., 26(5):1484-1509, 1997.
• [29] D. Simon. On the power of quantum computation. SIAM J. Comp., 26(5):1474-1483, 1997.