Quantum Threshold Gate Simulator
Xin Chen (email@example.com)
Advisor: Dr. Chris Pollett
In recent years interest in quantum computation has been steadily increasing. One reason for this is due to Shor's [S97] discovery of a polynomial time quantum algorithm for factoring, which is one of the strongest arguments in favor of the superiority of quantum computing models over classical ones. Since this discovery, many efforts have been made to find new, efficient quantum algorithms for classical problems and to develop quantum complexity theory. The goal of this research will be to develop a simulator which will aid in understanding the robustness of certain quantum algorithms.
The first such algorithm to be considered will be a scaled-down version of the algorithm in [FGHP99] which was used to show nondeterministic quantum polynomial time is equal to the counting hierarchy. The scaled-down version gives a way to simulate threshold circuits with small depth quantum circuits. The simulation is an improvement over what can be done with classical AND, OR, NOT circuits. Unfortunately, the acceptance model for these quantum circuits is unrealistic. We say a 1 is output if the quantum circuit accepts with a non-zero probability; otherwise, we say a 0 is output. So the question is how much error is introduced if we choose a more realistic acceptance criteria? Good formal estimates of this are somewhat difficult to directly calculate from the algorithm itself, so it would be interesting to do some simulations. It would also be interesting to simulate how errors would propagate in networks built out of such quantum units.
Two other algorithms we wish to consider were proposed in [GHMP02] and [AMP02]. These algorithms give exact simulations of Mod gates and narrow width branching programs in terms of simpler kinds of quantum circuits. We would like to study via simulations how sensitive these algorithms are to errors in the quantum gates used to build up the quantum circuits.
This project rises to the level of a Master's student's project because of the substantial work and mathematical maturity needed to understand the algorithms involved, let alone implement them. Also, there is a fair bit of UI work needed to make a nice environment for people to run experiments on such circuit networks.
The full project will be done when CS298 is completed. The following will be done by the end of CS297:
1. The first couple of assignments are to gain first-hand knowledge of the expressive power of threshold circuits. Write a program that allows one to simulate the classical, log-depth, AND,OR, NOT circuits for threshold gates on 10 bits.
2. Write a program that allows one to simluate the constant-depth threshold circuits for multiplication of two 5 bit numbers.
3. Write a program that classically simulates the scaled down version of [FGHP99] algorithm for threshold gates for the 5 bit case.
4. Do tests on the sensitivity of the algorithm in the 5 bit case. Write a GUI program that allows one to create and simulate small networks of 5 bit gates of this kind.
5. CS 297 Report. Suggest how to scale ideas of 3 and 4.
[AMP02] F.Ablayev, C.~Moore, and C.~Pollett. Quantum and Stochastic Branching Programs of Bounded Width. 29th International Colloquium on Automata, Languages, and Programming (ICALP). 2002. p.343--354. ECCC TR02-013.
[FGHP99] S. Fenner, F. Green, S. Homer, and R. Pruim. Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy. Proceedings of the Royal Society A (1999) 455, pp 3953--3966.
[GHMP02] F.Green, S.Homer, C.Moore, C.Pollett. Counting, Fanout, and the Complexity of Quantum ACC. Quantum Information and Computation. Vol. 2. No. 1. 2002. pp.35--65.
[NC00] Quantum Computation and Quantum Information. M.Nielson and I.Chuang. Cambridge. 2000.
[Pap94] Computational Complexity. C.Papapdimitriou. Addison Wesley. 1994.
[PS97] P.Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5): 1484-1509, 1997.
[Vol00] Introduction to Circuit Complexity. H.Vollmer. Springer-Verlag. 1990.
[Y93] A. C.-C. Yao. Quantum circuit complexity. Proc. 34th IEEE Symposium on Foundations of Computer Science, 352--361, 1993.