我們將會在這篇論文中提出量子群組測試的演算法。
群組測試這個問題已有五十年的歷史。
Clementi et al. 於 2001 年提出了 k-selective family。
而 Indyk 則在 2002 年提出了一個較簡單的 k-selective family 造法。
這個 k-selective family 正好可以用來解決群組測試問題。
這篇論文中我們先介紹 Grover 的量子搜尋演算法,
然後我們將合併 $k$-selective family 及量子搜尋演算法,
來解決群組測試問題。
這樣可以得到更好的時間複雜度。

We describe the quantum group testing algorithm.
Group testing problem has a history of research
in the early days of computer science.
In 2001, Clementi et al. introduce the k-selective family which
can be used to solve this problem.
Indyk provides a explicit construction method for the k-selective family
in 2002.
In this thesis, we first explain Grover's quantum search algorithm.
Then we involve the k-selective system with quantum computation
to solve the group testing problem with a better time complexity.

Contents
Chinese Abstract i
English Abstract ii
Contents iii
List of Figures v
List of Tables vi
1 Introduction 1
1.1 The Rest of This Thesis . . . . . . . . . . . . . . . . . . . . . 2
1.2 Notation and Symbols . . . . . . . . . . . . . . . . . . . . . . 2
2 Quantum Mechanics and Computation 5
2.1 Quantum bits . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Dirac Ket/Bra Notation . . . . . . . . . . . . . . . . . 5
2.1.2 Single qubit . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3 Multiple qubits . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Quantum Gates . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Single qubit gates . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Multiple qubit gates . . . . . . . . . . . . . . . . . . . 12
2.3 Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Quantum Algorithms . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.1 Quantum Search algorithm . . . . . . . . . . . . . . . . 22
3 Combinatorial Group Testing 27
3.1 Introduction to Group Testing . . . . . . . . . . . . . . . . . . 27
3.2 k-selective family . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 coin-weighting problem . . . . . . . . . . . . . . . . . . . . . . 36
4 Quantum Search with k-selective family 41
4.1 Prepared Unitary Operation . . . . . . . . . . . . . . . . . . . 43
4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 Conclusion 53
Bibliography 56

[1] Michel Boyer, Gilles Brassard, Peter Hyer, and Alain Tapp. Tight
bounds on quantum searching. Technical Report PP-1996-11, 30, 1996.
[2] Gilles Brassard, Peter Hyer, and Alain Tapp. Quantum counting. Lec-
ture Notes in Computer Science, 1443:820+, 1998.
[3] Bogdan S. Chlebus, Leszek Gasieniec, Anna Ostlin, and John Michael
Robson. Deterministic radio broadcasting. In Automata, Languages and
Programming, pages 717{728, 2000.
[4] Andrea E. F. Clementi, Angelo Monti, and Riccardo Silvestri. Selective
families, superimposed codes, and broadcasting on unknown radio networks.
In Proceedings of the twelfth annual ACM-SIAM symposium on
Discrete algorithms, pages 709{718. ACM Press, 2001.
[5] David Deutsch. Quantum theory, the Church-Turing principle and the
universal quantum computer. Proceedings of the Royal Society of London
Ser. A, A400:97{117, 1985.
[6] Ding-Zhu Du and Frank K. Hwang. Combinatorial Group Testing and
its Application. World Scientic, 2nd edition, 2000.
[7] Christoph Durr and Peter Hyer. A quantum algorithm for nding the
minimum, 1996.
[8] R. P. Feynman. Quantum-mechanical computers. Journal of the Optical
Society of America B-Optical Physics, 1:464, 1984.
[9] R. P. Feynman. Quantum-mechanical computers. Foundations of
Physics, 16:507{531, 1986.
[10] Richard P. Feynman. Simulating physics with computers. Int. J. of The.
Phys., 21:467, 1982.
[11] S. J. Glaser, T. Schulte-Herbruggen, M. Sieveking, O. Schedletzky, N. C.
Nielsen, O. W. Sorensen, and C. Griisigner. Unitary control in quantum
ensembles: Maximizing signal intensity in coherent spectroscopy.
Science, 280:421{425, 1998.
[12] G. A. Goldin. Gauge transformations for a family of nonlinear
schrodinger equations. nmp?, 4:6{11, 1997.
[13] Robert B. Griths and Chi-Sheng Niu. Semiclassical fourier transform
for quantum computation. Phys. Rev. Lett., 76:3228, 1996. Also arXiv,
quant-ph/951107.
[14] Lov. K. Grover. A fast quantum mechanical algorithm for database
search. In , 28th Annual ACM Symposium on the Theory of Computing
(STOC), pages 212{219, May 1996.
[15] Lov K. Grover. Quantum computers can search rapidly by using almost
any transformation. Los Alamos e-Print Archive, December 1997.
[16] Lov K. Grover. Quantum mechanics helps in searching for a needle in a
haystack. Los Alamos e-Print Archive, June 1997.
[17] Piotr Indyk. Explicit constructions of selectors and related combinatorial
structures, with applications. In Proceedings of the thirteenth annual
ACM-SIAM symposium on Discrete algorithms, pages 697{704. ACM
Press, 2002.
[18] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and
Quantum Information. Cambridge University Press, rst edition, 2002.
[19] Eleanor Rieel and Wolfgang Polak. An introduction to quantum
computing for non-physicists. ACM Computing Surveys, 32:300{335,
September 2000.
[20] Peter W. Shor. Algorithms for quantum computation: Discrete logarithms
and factoring. In IEEE Symposium on Foundations of Computer
Science, pages 124{134, 1994.
[21] Peter W. Shor. Polynomial-time algorithms for prime factorization and
discrete logarithms on a quantum computer. SIAM Journal on Com-
puting, 26(5):1484{1509, 1997.
[22] David R. Simon. On the power of quantum computation. In Proceed-
ings of the 35th Annual Symposium on Foundations of Computer Sci-
ence, pages 116{123, Los Alamitos, CA, 1994. Institute of Electrical and
Electronic Engineers Computer Society Press.