Advisor: Dr. Chris Pollett

Committee Members: Prof. Robert Chun, Department of Computer Science, (chun@cs.sjsu.edu) Prof. Walter W. Kirchherr, Department of Computer Science, (kirch@cs.sjsu.edu)

Abstract:

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 algorithm.

Spalek [S02] gives a way of simulating threshold gate with small depth quantum circuits in the exact acceptance model. The simulation is an improvement over what can be done with classical AND, OR, NOT circuits. Yet, Spalek's algorithm assumes that we can perform certain rotation operator to arbitrary accuracy. So the question is how much error is introduced if we choose a more realistic acceptance criterion. Good formal estimates of this are somewhat difficult to directly calculate from the algorithm itself, so it would be interesting to do some simulations. This is the goal of this project.

CS297 Results

• Implemented a program that allows one to simulate the classical log-depth, AND, OR, NOT circuits for threshold gates on 10 bits. This deliverable helped me to get the feeling of simulating threshold gate in classical ways.
• Implemented a simulator which can simulate the log*-depth threshold circuits for multiplication on two 5 bits numbers. By doing this, I gained first-hand knowledge of the expressive power of threshold circuits.
• Implemented a quantum circuit for value gate. This deliverable took me to the doorway of my final simulator. It gave me the insight of how the quantum algorithm works. By doing this program, I became reasonably proficient at the substantial mathematical maturity needed to understand the algorithms involved. However, this program is a naive implementation of algorithms described in [S02]. For now, both the space complexity and the time complexity are exponential, and thus, it is infeasible on multi-qubits.
• Explored an idea of reducing both the space and the time complexity described above from exponential to polynomial. I will implement this idea this semester, which is targeting to compute on 30-qubits value gate.

Proposed Schedule

Key Deliverables:

• Simulator:
  • Give n bits input, the simulator can simulate a quantum circuit that performs the functions of a classical threshold gate.
  • The simulator supports ways of experiments with error models applied to the base gates.
  • The simulator must be implemented in a very efficient way, so that it is feasible on multi-qubits. Our goal is 30 qubits. The current best of anyoneÆs quantum simulator is 15 qubits.
• Report
  • Description of the idea that can reduce both the space complexity and time complexity from exponential to polynomial.
  • Description of the matrices that represent for each quantum gate in this algorithm.
  • Description of the techniques used in my implementation, such as data structure and class organization.
  • Description of test results from introducing errors to the base gates.

Innovations and Challenges

• In practice, the acceptance model for quantum circuits is unrealistic due to its assumption of exactly prepared quantum states. It is difficult to accurately estimate effects of errors by calculating from the algorithm itself. My project is to do a simulator that will aid in understanding the robustness of this quantum algorithm.
• Substantial mathematical maturity is needed to understand the quantum mechanics.
• A naive implementation of [S02] is infeasible. Both the time and space complexity are exponential. For five qubits case, we will need at least 8G bytes memories, and the runtime is also unacceptable. A more efficient implementation idea is needed, which can reduce both the time and space complexity to polynomial.
• The algorithm needs calculations on huge size matrices (for n-qubits, the space is 2^O(nlog(n) ). Even the sparse matrix representation requires exponential space and so to the runtime. We are designing even more efficient implementation techniques, based on deeper understanding of the quantum value gate algorithm.
• A good data structure is needed. Also, special implementation techniques are needed.
• Find a suitable way to introduce error scheme to existing system without increasing much on space and time complexity.

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.

[I94] Circuit Complexity and Neural Networks. Ian Parberry. The Mit Press. 1994.

[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.

[S02] R. Spalek. Quantum Circuits with Unbounded Fan-out. STACS 2003 v2. 2002.

[Vol00] Introduction to Circuit Complexity. H.Vollmer. Springer-Verlag. 2000.

[Y93] A. C.-C. Yao. Quantum circuit complexity. Proc. 34th IEEE Symposium on Foundations of Computer Science, 352--361, 1993.