soft question - Areas of computer science required for quantum computing

What knowledge of computer science should I have, to be able to pursue research in quantum computing. I am a Physics undergrad and would take three core courses in QM, before the completion of my degree. SO I guess necessary QM would be done. What about computer science?

Answer

It is most helpful to know about reversible computation, a bit about circuit complexity, and about universal sets of gates in classical computation (e.g. the standard spiel about the gate set {AND, OR, NOT}, or for that matter the single gate NAND, being sufficient to compute any boolean function). Probably all that you need to know about both of these subjects is contained in Nielsen & Chaung, which still retains it's status as the most popular introductory text book.

Most of the problems which are commonly treated in quantum computation have either a number-theoretic flavour (involving integers modulo N for some integer N; or possibly just vectors over the integers modulo 2), or a graph-theoretic flavour. Having a very basic familiarity with number theory — prime numbers, multiplicative units, greatest common divisors, and so forth — and with graphs is a good idea. Any good first-year textbook on discrete mathematics which touches on these topics ought to be adequate.

Aside from the above, quantum computing is a highly multidisciplinary field with a broad range of topics. This means that beyond the basics, what you should study as background depends strongly on what it is that you're interested in learning about, or in researching. For the essentials of quantum computing, just the above will do a good job for anything which is not on the way to being an ongoing research project.

Depending on what further subjects you want to pursue, there are obviously other things you might want to investigate as background. Here are two which are more likely to be useful to you in forming a perspective on subjects of interest.

1. 
   

   In many topics of quantum information theory, semidefinite programming often plays a useful role, as optimisation questions in quantum information involve a constraint of a density operator being positive semidefinite.

   
   


2. 
   

   If you'd like a big-picture perspective on the power or limitation of quantum computers, you should learn some complexity theory, especially if you would like eventually to investigate problems such as the difference in computational power between the complexity classes

   
   
   
   
   • NP (the class of difficult problems of P versus NP fame), and
   
   
   • BQP (the class of problems efficiently solvable by an ideal quantum computer);
   
   
   
   

   whose computational power are currently thought to be incomparable, i.e. neither more powerful than the other.

   
   
   

Finally, many special topics in quantum computation are either explicit extensions of classical computational theory, or can in any case be construed as a natural generalization of a classical computational subject to the quantum mechanical régime. So, for any subject which you hear about in quantum computation that strikes you as interesting, you should consider investigating whether there's a classical subject which might give you information regarding the quantum generalization.