4
$\begingroup$

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a series of quantum SWAP gates, which are composed of three CNOT gates respectively; the shifting contributes to the total circuit complexity.

So where does the difference come from? Is it due to the physical implementation of qubits?

$\endgroup$
  • $\begingroup$ I was interested in quantum computing and found a course by Vazriani on edx.org (edx.org/course/uc-berkeleyx/…) a very good introduction. He explains CNOT gates and SWAP gates pretty quickly. $\endgroup$ – Jake Oct 25 '14 at 2:48
11
$\begingroup$

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special subclass of quantum operations.

As a technology

We're still working on how to implement a large-scale quantum computer. Part of the reason for this is that it is a non-trivial engineering problem to devise quantum memories on which we can reliably act.

Many of the proposed architectures involve physical qubits which are in a fixed(-ish) position, relative to the others. Whether these are quantum dots (attached to a substrate), ions in a linear trap (mobile but often penned in between two other ions), or even nuclear spins in liquid NMR (locations fixed mostly by the chemical bonds within each molecule), those qubits don't have much freedom to move relative to the ones you want it to interact with. You can't necessarily shuffle them around like cups and balls.

The fixed wires in a classical circuit get around this physical location problem by being physically extended. The wire acts as if tracing out the trajectory of "moving" logical bits, and may weave around each other somewhat between two logic gates. When we draw quantum circuit diagrams, we're dreaming of this — but at least one of the dimensions in the diagram represents not space, but time between the physical operations which we perform. Not many physical architectures for quantum information admit that sort of physical extension, while keeping the quantum bit coherent and available to be acted upon. If locations are more or less fixed, this prevents us from literally swapping around the qubits.

In summary, in quantum implementation, we can't be confident that SWAP operations will be easily achievable "in hardware", i.e. by swapping around the physical qubits. We thus have to resort to be achieving SWAP operations "in software" — by performing suitable operations to 'transport' the information from one physical qubit to another. Thus our interest in decomposing SWAP in terms of elementary gates.

As a model of computation

As a part of theory of computation, you are exactly right: decompositions of SWAP are only a curiousity, much like the logical universality of the NAND gate. It is worth taking note of, in elementary courses; but much beyond that we treat decompositions of SWAP almost exactly as seriously as we do the decomposition of classical algorithms into NAND gates — not very seriously, most of the time. So long as we consider a model of computation in which elementary gates have a constant cost and which generate SWAP, then SWAP can be performed with at most a constant cost — and if the cost due to SWAP gates does not dominate the run-time of the algorithm, then talking about them doesn't really shed any insight onto the complexity of a problem.

Of course, because of the technological promise of quantum computation, the technical difficulty in implementing quantum computers, not to mention the promise of any technique (including classical ones) to simulate bits of quantum mechanics, specialized and related models of computation have attracted some theoretical interest. One of these are "matchgate" circuits, which may be described as unitary circuits in which

  • Qubits are arranged in a linear array;
  • Only two-qubit nearest-neighbor unitary transformations are allowed (and possibly Hadamard operations, on the first qubit only);
  • All two-qubit operations are of the form $$\begin{bmatrix} a_{00} & 0 & 0 & a_{01} \\ 0 & b_{00} & b_{01} & 0 \\ 0 & b_{10} & b_{11} & 0 \\ a_{10} & 0 & 0 & a_{11} \end{bmatrix} \quad\text{where $\begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix}, \begin{bmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{bmatrix} \in \mathrm{SU}(2)$}$$ i.e., acting unitarily (with determinant 1) on the odd- and even-parity subspaces of the pair of qubits.

These computations can be efficiently simulated by classical computers (provided that the coefficients are efficiently computable, etc.) However, if you consider circuits which have these gates, and also SWAP gates, they become universal for quantum computation. The same holds if you allow the gates to act even on next-nearest neighbour qubits, or allow Hadamard operations on other lines than just the first. What appear to be trivial modifications of the model, which one could imagine performing by just moving qubits around, transform a model which is tractible to simulate to one which (we think) is intractible to simulate. Nor, obviously, can we decompose SWAP into gates which are allowed.

In summary

From a theoretical perspective, SWAP operations are exactly as boring as you think they should be, for much of the research in quantum computation. But a model of computation is a mathematical model of something we hope to achieve in hardware: the model is not necessarily representative of reality. And even if SWAP is boring in one model of computation, that doesn't mean it is boring in another model!

We are complacent about SWAP in classical computation because electronic computers are a mature technology in which these details are mostly safe to ignore. As soon as you switch models of computation, you must check your computational assumptions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is a dark area between theory and implementation. $\endgroup$ – ZhangJun Oct 25 '14 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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