This is a question you might get asked fairly often if you ever mention that you do research in quantum physics. You might even be asked if you are a Prime Minister visiting a research facility on the topic. So among all the questions I would expect to be asked, this is not a particularly surprising one. Except on my PhD viva exam, when I really did not expect it. Particularly in the form it was phrased: “How can you tell if a machine is a quantum computer? If aliens came to Earth and tried to sell you a quantum computer, what could you do to be certain they were not fooling you?”. I didn’t expect alien sales to be part of my viva, that’s for sure! Fortunately for me, some conversations I had previously had with experimentalists at the Centre for Quantum Photonics helped me give an answer that satisfied my examiners. However, I came out from the exam with the nagging feeling that *that* should have been a much easier question to answer.

In any standard course on quantum computing and its implementations, usually one learns about the DiVincenzo criteria, which states that a quantum computer should have:

- A scalable physical system with well-characterized qubits.
- The ability to initialize the state of the qubits to a simple ﬁducial state.
- Long relevant decoherence times, much longer than gate operation times.
- A “universal” set of quantum gates.
- A qubit-specific measurement capability.

These criteria were formulated in the year 2000 with a specific computational model in mind, the circuit model. Since then, other ways of implementing quantum computing have sprung out, from computational models (such as cluster state and adiabatic models) to physical implementations that don’t deal with qubits but rather with continuous variable systems. Many of these new developments don’t quite fit the DiVincenzo criteria, so are there any better definitions of what quantum computers are?

Searching through the scientific literature, and through statements of experts to the media, we can find five distinct ways in which to specify what a quantum computer is:

**Abstract theoretical definitions**: Such is Deutsch’s definition in his 1984 paper where he formulates a physical version of the Church-Turing thesis that is compatible with quantum theory: “*a quantum computer is a […] quantum generalization of the class of Turing machines*”. Or Feynman’s: “*It’s not a Turing machine, but a machine of a different kind*”. These definitions are very abstract and lack details and specifications on the structural components, making them not very useful in practical scenarios.**Implicit definitions**: A quantum computer is not defined necessarily by its components but rather by stating that it uses the laws of quantum mechanics to perform computation. As true as this definition is, it is no help when trying to decide whether a computer is quantum or not. How can we assert from outside which laws govern the logical operations inside?**Comparative definitions**: A quantum computer is a device that can outperform classical computers. While we certainly expect them to be able to solve problems that would otherwise be outside our reach if we only had access to classical computers, relying on the classification of problems in complexity theory is uncertain business, as this classification is not written in stone and evolves as the field develops.**Constructive definitions**: These definitions specify what a quantum computer is by stating their components or the way information is processed. For example, defining the quantum computer as a machine that fulfils the DiVincenzo criteria falls in this category. This kind of definitions share the characteristic of being narrow and tied to a specific implementation, and therefore not general enough to apply to all architectures, physical implementations and computational models.**Operational definitions**: The quantum computer is fully defined by what it does, if a machine acts like a quantum computer, it is a quantum computer. The definition makes no assumptions about the theory of computation or the nature of physical reality, and therefore different interpretations of quantum mechanics should agree that the machine is a quantum computer.

There is an excellent paper which intends to figure out a useful operational definition for quantum computers that will stand the test of time, and by making no reference to how the computer exactly works, it should still hold in years to come when new techniques have been developed. As end users we care mainly about performance, and not necessarily about the nitty-gritty details of how that performance is achieved. As an example, how many of you understand all the complexity of the device you are using to read this blogpost? I certainly don’t.

The proposed operational definition of a quantum computer in this paper is as follows:

“We define a quantum computer as a device that can run a quantum algorithm efficiently, where a quantum algorithm is a classical bit string that encodes a series of quantum operations. The quantum computer should be able to take this string as input and produce another one as output. The probability distribution of the output should be consistent with the predictions of quantum theory. Finally, the time it takes the computer to produce the output should be in agreement with the difficulty of the algorithm.”

Note that this definition makes no mention of the way in which the quantum operations are performed, and therefore is open to different models of computation. The time constraint in this definition is crucial, as it excludes classical computers, because, for example, if we ran Shor’s factoring algorithm in a quantum computer we would expect an answer in polynomial time and a classical computer would require exponential time. But also this definition doesn’t depend on the current classification of complexity problems, as “*the difficulty of the algorithm*” mentioned in the definition would refer to the difficulty of a particular problem at the time of the test.

It is also worth noting that both the input and output are classical bit strings. After all, the input and output are the interactions of the machine with the controller, which lives in a classical world. The *quantum program* will be the encoding of the operations of a particular quantum algorithm, which will be part of the input string along with the initial state of the quantum computer. The instructions for generating the initial state on the quantum computer must have an efficient classical representation, this is the case for all computational models. It is worth noting that for all the current proposals of quantum computers, some classical pre and post-processing are assumed, which agrees with the above definition as long as this classical processing takes only polynomial time in the problem size.

In this paper they also have a set of criteria for building a quantum computer, that is general enough to fit all computational models (currently known) and all physical implementations proposed. It is based on 4 statements:

**Any quantum computer should have a quantum memory**. Quantum memory is the broad term used to state that the quantum computer must have the capability of efficiently representing any computable pure quantum state (of a size accordant with the size of the computer) in its internal degrees of freedom. This quantum state will not have, in general, an efficient classical representation.**Any quantum computer must facilitate a controlled quantum evolution of the quantum memory, which allows for universal quantum computation**. By controlled quantum evolution, the authors mean that the evolution of the internal state of the quantum computer must follow the laws of quantum mechanics, and will ultimately be controlled by the end user.**Any quantum computer must have a method for cooling the quantum memory**. Entropy is accumulated in the quantum memory as a product of a previous computation or because of the presence of errors due to noise from the environment.*Cooling*refers to information-theoretic cooling, where the entropy is extracted from the quantum memory. It encompasses the process of initialisation of the quantum memory as well as the error correction procedure.**Any quantum computer must provide a readout mechanism for subsets of the quantum memory**. The computer must have a mechanism to translate the outcome of the computation to classical bits for the controller to obtain the result of the computation. The authors refer to subsets of measurements as during most error correcting procedures, there are intermediate measurements used to assess the presence of errors, and this kind of measurements are not of much use to the end user.

There are two other essential characteristics for a quantum computer the authors require:

**Fault-tolerance**: Fluctuations from the environment can cause stochastic errors to appear in the quantum computer. If a quantum computer still works according to its definition in the presence of such errors, it will be deemed fault-tolerant. This will be the case if the computer uses some form of error correction that has an error threshold (maximum size of individual errors) higher than the errors caused by the environment.**Scalability**: Currently any claims of scalability in any particular physical implementation of a quantum computer are predictions, as no reasonably large quantum computer exists. Theoretically, a quantum computer is scalable if the resources required to run the same polynomial time algorithm on a larger input scaled polynomially on the size of the input. What makes a particular architecture scalable depends heavily on the architecture and technological prediction and it is difficult to make general statements without getting into the detail any given implementation. An excellent read on this subject can be found in the Quantum Pontiff blog post “Climbing Mount Scalable”.

It is perhaps because we don’t have a functioning large-scale quantum computer that it is difficult to give accurate definitions without hiding behind the “spooky” laws of quantum mechanics. At the end of the day definitions are not the most important thing, and proof of that is that Nielsen & Chuang, the must-read book for any quantum information scientist, does not define what a quantum computer is and rather lets the reader build up an intuition. But it is important to know what we talk about when we talk about quantum computers, for us to be able to make informed decisions about whether a machine is a quantum computer or not, in case aliens or someone else came to us with sales pitch.

## 2 comments on “What is a quantum computer?”