CS297 Proposal
Quantum Threshold Gate Simulator
Xin Chen (xinchen_2002@yahoo.com)
Advisor: Dr. Chris Pollett
Description:
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.
Schedule:
Week 1:
Aug 26-30 | Prepare 297 proposal. |
Week 2:
Sep 2-6 | Read Part IV [Pap94] |
Week 3:
Sep 9-13 | Read Part V [Pap94]. Del 1 due |
Week 4:
Sep 16-20 | Read [Vol00] Ch1-2 |
Week 5:
Sep 23-27 | Read [Vol00] Ch 4. Del 2 |
Week 6:
Sep 30-Oct 4 | Read [NC00] Ch1-2 |
Week 7:
Oct 7-11 | Read [NC00] Ch4-5 |
Week 8:
Oct 14-18 | Read [FGHP99] |
Week 9:
Oct 21-25 | Read [NC00] Ch6-7. Del 3 |
Week 10:
Oct 28-Nov 1 | Read [GHMP02] |
Week 11:
Nov 4-8 | Read [AMP02] |
Week 12-13:
Nov 11-22 | Work on and Finish Deliverable 4. |
Week 14-16:
Nov 25-Dec 9 | Write CS 297 Report. |
Deliverables:
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.
References:
[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.
|