# Von Neumann architectures and quantum computing

Can you do quantum computing in a von neuman architecture? If not, why? What is the constraint? If you control a qbit, can a quantum computer use the von neuman architecture?

Thanks.

What do you mean by von Neumann architecture?

I'll use the Wikipedia definition, and say that it's a computer which keeps its program and its data in the same random-access memory. This works well as a theoretical model of a quantum computer, but there are severe drawbacks to implementing such a device. In particular, for a quantum computer, the data has to be quantum. If the data and program are stored in the same memory device, this would imply that the program has to be quantum, as well. So the computer would then have to be able to implement a superposition of instructions in its instruction set. This is orders of magnitude more difficult experimentally than just having the memory in superposition.

In fact, even indirect memory retrieval, including RAM, pointers, and so forth, appears to be quite difficult to implement experimentally.

This has resulted in the default model of a quantum computer being the uniform quantum circuit model, which is both easier to imagine implementing experimentally and tractable to deal with theoretically from a TCS perspective. The circuit model is able to simulate the von Neumann architecture with only a polynomial slowdown, so quantum complexity classes are not changed by this change of model.

• I would have thought the slowdown is at most constant when simulating a von Neumann architecture, but polynomial for a von Neumann architecture machine simulating the circuit model. Jun 9, 2011 at 1:36
• @Joe: It's really time-consuming to simulate indirect addressing with the circuit model. Jun 9, 2011 at 1:39
• Ah I see. That makes sense. Jun 9, 2011 at 1:51
• Absolutely agree, the addressing is a problem. Jun 9, 2011 at 14:05
• Except for straight-line programs, I should think that the program would have to be quantum, even for a Harvard architecture: consider what happens in a conditional jump on quantum data. If all one has are straight-line programs, then the circuit model is much easier, I should think. Sep 22, 2011 at 15:52

There is a recent article on implementing a quantum von Neumann architecture. They do this via superconducting qubits, of course the implementation is very small, with only 7 quantum parts: two superconducting qubits, a quantum bus, two quantum memories, and two zeroing registers. This allows their quantum CPU to perform one-, two-, and three-qubit gates on qubits, and the memory allows (data) qubits to be written, read out, and zeroed. As is mentioned in Peter Shor's answer, implementing a quantum superposition of gates is very difficult, and so the program is stored classically.

There is a Nielsen and Chuang result about programmable quantum gate arrays due to that states of program should be orthogonal (if it is deterministic case, but stochastic case is other long story). So you may store both program and data in the same place, but formally the program is “quasi-classical,” because you should not use superpositions (despite the fact, that you could do it, in principle). I think it better should be called a “modified Harvard” architecture, despite I myself called that von Neumann architecture of quantum computer sometimes.

The Von Neumann architecture relies heavily on memory. One of the biggest challenge in implementation of qubits being coherence time, that is, the time for which a qubit can maintain its state before being flipped, which it is very short. Also, every operation done in a quantum computer has to be reversible, this is not the case in classical computing architectures.

Most of the quantum algorithms designed thus far are ad hoc. There is not yet a universal quantum computer, to which you give code and it executes it as in everyday computers. From a quantum algorithm, we can design a circuit that implements it, which can even depend on the size of the instance of the problem to be solved (i.e. you could have to initialize log(n) qubit registers for a problem of size n). This most likely implies that there will always be classical computers that will be required to run quantum computers as a subroutine.

• The quantum circuit architecture with gates controlled by a classical computer indeed acts as a universal quantum computer. You don't need everything to be quantum in order for your quantum computer to simulate any quantum computation. Jun 14, 2011 at 3:23
• Peter: There is theoretical problem with description of such device in some universal way, due to quantum-to-classical transition question. If to consider instead of classical computer an equivalent quantum device, we should not think about that at all. Jun 15, 2011 at 15:11
• There is no need to ensure that all operations in a quantum computer need to be reversible. In fact, measurement-based quantum computing primarily uses non-reversible operations. Nov 16, 2011 at 15:41