Colin P. Williams is a Senior Research Scientist (SRS), and Program Manager for Advanced Computing Paradigms, in the Mission Software Computing Autonomy and Networking (MSCAN) Program Office at the Jet Propulsion Laboratory, California Institute of Technology. He holds a Ph.D. in artificial intelligence from the University of Edinburgh, a M.Sc. and D.I.C. in atmospheric physics and dynamics from Imperial College, University of London, and a B.Sc. in mathematical physics from the University of Nottingham. He was formerly a research assistant in quantum cosmology to Prof. Stephen W. Hawking, at the University of Cambridge, and a research computer scientist at Xerox PARC, one of Silicon Valley’s best known computer science think tanks.

Colin's research interests have spanned many areas connecting physics with computer science. In his thesis work Colin developed an artificial intelligence system for reasoning about the physical world via qualitative and quantitative differential equations. He then became interested in the links between statistical physics and computer science, invented the theory of computational phase transitions, and applied it understanding the deep structure of NP-Complete problems. Later, Colin became interested in the connections between quantum physics and computer science. In 1998 he published the first book on quantum computing, and followed it up with two others, launched the Quantum Computing Technologies Group at JPL, and quickly broadened its scope to include research on quantum communications and quantum sensors.

Lately, Colin has been expanding his interests to include cognitive computing, virtual environments, computational material design, and intelligent energy applications. In addition, has been developing quantum algorithms for solving computationally hard problems such as Boolean satisfiability and other NP-Complete problems, designing quantum circuits for two-dimensional quantum wavelet (and other) transforms, and devising protocols for Space-to-Earth quantum image transfer, and long distance quantum communications using quantum repeaters. In addition, he has developed powerful software for automatically designing quantum circuits that can implement any quantum algorithm and automatically specializing those circuits for implementation in spin-based, and charge-based quantum computing hardware.

Colin has written five books, and been a guest editor of two special issues, one on computational phase transitions, and the other on quantum computing. He co-invented and holds patents on “quantum lithography” – a photolithographic scheme for fabricating semiconductor structures with dimensions arbitrarily smaller than the wavelength of the light used – and “non-unitary probabilistic quantum computing” – a scheme that greatly enlarges the space of algorithms implementable quantum mechanically – and he has another patent pending on CAD tool for quantum computers. From 2000-2002 Colin was on remote assignment from JPL as an acting Associate Professor of Computer Science at Stanford University where he taught courses on quantum computing and communications, and computer algebra using Mathematica.

Colin's research interests have spanned many areas connecting physics with computer science.

• Quantum computing – quantum algorithms, automated circuit design, fault-tolerance
• Quantum communications – Earth-to-Space quantum communications, quantum repeaters
• Cognitive computing – computer hardware analogs of human cortex
• Artificial intelligence – logic programming, constraint satisfaction
• Virtual environments – conveying the experience of a remote environments locally
• Quantum lithography – making sub-wavelength structures using entangled photons
• Quantum metrology – gravitational tomography using quantum gravity gradiometers

Publications

1. “A Random Matrix Model of the Quantum Adiabatic Algorithm”, D. Mitchell, C. Adami, and C. P. Williams, Phys. Rev. A 71, 052324 (2005).
2. “Optimal Quantum Circuits for General 2-Qubit Gates,” F. Vatan and C. P. Williams, Physical Re-view A, Volume 69, 032315 (2004).
3. “Construction of a Quantum Repeater with Linear Optics,”, P. Kok, C. P. Williams, and J. P. Dowling, Physical Review A 68 (2), 022301 AUG (2003).
4. “Non-Unitary Probabilistic Quantum Computing”, R. Gingrich and C. P. Williams, in Proc. Of the Winter International Symposium on Information and Communication Technologies, Cancun, Mex-ico, Jan. 5th-8th (2004).
5. “From Linear Optical Quantum Computing to Heisenberg-Limited Interferometry”, H. Lee, P. Kok, C. P. Williams, and J. P. Dowling, Special Issue on "Fluctuations and Noise in Photonics and Quantum Optics" (Herman Haus Memorial Issue), J. Opt. B: Quantum Semiclass. Opt. 6 (2004) S1-S5.
6. “Probabilistic Non-Unitary Quantum Computing,” C. P. Williams, in Proc. SPIE Defense and Se-curity Symposium, Orlando, Florida, 12-16th April (2004).
7. “Computational Synthesis of Any n-Qubit Pure or Mixed State,” L. Song, and C. P. Williams, in Proceedings of SPIE, Volume 5105, Aerosense, 21st-22nd April 2003, Orlando, Florida, April (2003), pp.195-203.
8. “Linear Optics and Projective Measurements for Fun and Profit,” P. Kok, H. Lee, C. P. Williams, and J. P. Dowling, in Proceedings of SPIE First International Symposium on Fluctuations and Noise, Santa Fe, New Mexico (2003).
9. “Universal Quantum Gates for Single Cooper Pair Box Based Quantum Computing,” P. Echternach, C. P. Williams, S.C. Dultz, P. Delsing, S. L. Braunstein, J. P. Dowling, Quantum Information and Computation, Vol. 1, Special (2001), pp.143-150.
10. “Quantum Search Algorithms in Science and Engineering”, Colin P. Williams, Computing in Science and Engineering, IEEE Computer Society, April (2001).
11. “Quantum Interferometric Optical Lithography: Towards Arbitrary Two-dimensional Patterns,” Pieter Kok, Agedi N. Boto, Daniel S. Abrams, Colin P. Williams, Samuel L. Braunstein, and Jonathan P. Dowling, Physical Review A 63, 063407 (2001).
12. “Quantum Atomic Clock Synchronization based on Shared Prior Entanglement”, Richard Jozsa, Daniel Abrams, Colin P. Williams and Jonathan P. Dowling, Physical Review Letters, Volume 85, Issue 9, 28th August (2000) pp.2010-2013.
13. “Quantum Computing: the Final Frontier?”, Richard J. Hughes and Colin P. Williams, IEEE Intelli-gent Systems and their Applications, Vol.15, No. 5, September/October (2000).
14. “Quantum Interferometric Optical Lithography: Exploiting Entanglement to Beat the Diffraction Limit”, Agedi N. Boto, Pieter Kok, Daniel S. Abrams, Samuel L. Braunstein, Colin P. Williams, and Jonathan P. Dowling, Physical Review Letters, Volume 85, Issue 13, 25th September (2000) pp.2733-2736.
15. “Generalized Quantum Search with Parallelism”, Robert M. Gingrich, Colin P. Williams and Nicolas J. Cerf, Physical Review A, Volume 61, 052313, 19th April (2000).
16. “Nested Quantum Search and Structured Problems”, by Nicolas Cerf, Lov Grover, Colin P. Wil-liams, Physical Review A, Volume 61, 032303, 9th February (2000).
17. “Maxwell Duality, Lorentz Invariance, and Topological Phase”, Jonathan P. Dowling, Colin P. Wil-liams, and James Franson, Physical Review Letters, 83 (1999) pp.2486-2489.
18. “Quantum Neural Networks”, by Michail Zak & Colin P. Williams, International Journal of Theoreti-cal Physics, Vol. 37, No. 2, February (1998) pp651-684.
19. “Automated (Genetic) Design of Quantum Circuits”, by Colin P. Williams & Alex Gray, Springer-Verlag, Lecture Notes in Computer Science, Volume 1509 (1999), pp.113-125.
20. “Quantum Recurrent Networks for Simulating Stochastic Processes”, by Michail Zak & Colin P. Williams, (Springer-Verlag) Springer-Verlag, Lecture Notes in Computer Science, Volume 1509 (1999), pp.75-88.
21. “Quantum Wavelet Transforms”, by Colin P. Williams & Amir Fijany, Springer-Verlag, Lecture Notes in Computer Science, Volume 1509 (1999), pp.10-33.
22. “Phase Transitions & the Search Problem”, Artificial Intelligence Journal, Vol. 81, Numbers 1-2, pp1-15 (1996).
23. "Exploiting the Deep Structure of Constraint Problems", Artificial Intelligence Journal, Vol. 70, pp73-117, November (1994).
24. "The Hardest Constraint Problems: A Double Phase Transition", Artificial Intelligence Journal, Oc-tober (1994).
25. "Typicality of Phase Transitions in Search", Computational Intelligence, Vol. 9, No. 3, pp221-238 (1993)

Patents

1. US 6,252,665 Lithography Using Quantum Entangled Particles (Issued 26th June 2001)
2. US 6,480,283 Lithography System Using Quantum Entangled Photons (Issued 12th November 2002)
3. US 6,583,881 Lithography Using Quantum Entangled Particles (Issued 24th June 2003)
4. US 6,630,290 Lithography Using Quantum Entangled Particles (Issued 7th October 2003)
5. US 7,590,607B2 Non-Unitary Probabilistic Computing Circuit and Method (Issued Sept. 15th 2009)