In 1938, in a famous paper, Alan Turing proved that you could simulate any Turing machine with the following six primitive operations:
1. Move one square to the right
2. Move one square to the left
3. Write a symbol on the current square
4. Read any symbols on the current square
5. Erase any symbols on the current square
6. Do nothing
Is there an analogous set of minimum primitive operations for a quantum computer? Or is it the same set?
I would also include "the read head has to contain a small finite state machine" as one of the requirements.
Anyways, the answer is yes it's basically the same requirements. The main difference is that the tape symbols are replaced by qubits, and the read head also needs to have a qubit. Correspondingly, "read the symbol" is replaced by "measure the qubit on the tape" and "write/erase the symbol" is replaced by "apply a two qubit operation between the qubit on the tape and the qubit in the read head".
In terms of a gate-based model, almost any single two-qubit gate (i.e. a random gate) is universal. Otherwise, there's simple gate sets with two gates which are universal, such as Toffoli + Hadamard.
