Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
+1 I would just add some basic automata theory. (Once I investigated simulating a finite state machine in a quantum computer, and it was possible after transforming the FSM into a reversible one. That's the key. Computations have to be reversible. They cannot lose information.) –  Mike Dunlavey Jul 18 '12 at 14:52
@MikeDunlavey: it depends entirely one what the OP is looking to get into. While there is a line of research into quantum versions of finite automata (c.f. my final paragraph), I'm not certain as to its general utility as background for quantum computation. I would really prefer to stress circuits, and reversible circuits in particular, in that case. –  Niel de Beaudrap Jul 18 '12 at 14:58
@NieldeBeaudrap: What abt quantum crytopgraphy? How much cryptography is needed? –  ramanujan_dirac Oct 14 '12 at 21:58
@ramanujan_dirac: you should ask this as a separate question. To be quite honest, apart from the very basic concepts of the Vernam cipher (i.e. the one time pad), and notions of entropy or the distance between probability distributions, and perhaps the DiFinetti theorem, I do not know what concepts of cryptography/probability may be pertinent to quantum cryptography, as it is not my area of expertise. –  Niel de Beaudrap Oct 14 '12 at 22:16
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.