Quantum computing (QC) — though still in its experimental stages at present — is widely held to be the future of computing. A viable quantum computer would enable not just more and faster calculations, it would also make possible new types of calculations that current, binary bit-based computers are incapable of (like a single value-state equal to 53% “yes” / 47% “no”).
The theoretical, informational unit of QC is the quantum bit or ‘qubit’. The posited qubit is comprised of an actual quantum particle (e.g., a photon) in a superposition state (a combination of two basis states), that is, one whose polarization state (or spin state, if an electron) is both ‘vertical’ and ‘horizontal’ simultaneously. This superposition state is what distinguishes QC from normal digital computing (with bit values that are either ‘0’ or ‘1’); the value of a qubit can be ‘0’, ‘1’ or both at once.
Imagine that all computational values (or states) are located on the surface of a sphere. In conventional (classical) digital computing, the value/state of a bit can be either on the sphere’s ‘north pole’ (a ‘0’) or ‘south pole’ (‘1’); in QC the value/state of a qubit could lie on the sphere’s equator (see diagram, below) — a superposition state inaccessible to classical computing — or anywhere else in between.
[right] A Bloch sphere representation of a qubit. The possible states for a single qubit can be visualized using a Bloch sphere. Represented on such a sphere, a classical bit could only be at the “North Pole” or the “South Pole”, in the locations where |0> and |1> are respectively. The rest of the surface of the sphere is inaccessible to a classical bit, but a pure qubit state can be represented by any point on the surface. For example the pure qubit state {|0 > + i|1 > / {sqrt{2}} would lie on the equator of the sphere, on the positive y axis.
The Challenges of Quantum Computing
One of the biggest challenges with the current technological model of QC is that actual quantum particles do not retain their value states for very long, that is, they are time dependent and are also subject to decay and “decoherence” effects from fluctuating electromagnetic fields and other sources.
Up until quite recently, extremely low temperatures — near absolute zero — were required to preserve a qubit’s altered (informational) state. However, recent advances with diamond-based materials that exploit Nitrogen gaps or “vacancies” in the diamond’s crystal lattice allow spin qubits to be stable enough to operate (i.e., remain coherent) at room temperature — but only for very short periods of time (microseconds)..
And other challenges remain, such as the problem of scalability. For example, a graph using the current qubit architecture of n qubits would be “exponentially large” (as a function of n) where each vertex (i.e., each crossing of graph lines*) would occupy a different spatial location. This means that the current approach to QC is non-scalable (too much “overhead”). Thus, despite the many such non-scalable implementations of the quantum walk carried out to date, efficient, universal quantum computation has remained beyond reach.
* With a superposition photon, each vertex on the graph would represent a discreet wave packet (of light).
The New Model – Approaching Universal Quantum Computation
Addressing these current obstacles to the attainment of scalable, quantum-based computation, a team of researchers from the Institute for Quantum Computing (IQC) in Waterloo, Ontario, Canada, have proposed a new theoretical model: Universal computation by multi-particle quantum walk. The ‘quantum walk’ here is the quantum mechanical analog of the ‘random walk’ formalization from classical mathematics/physics, wherein the path taken by a molecule (e.g., in a liquid or gas), or a foraging animal, or even the price fluctuation of a particular stock, consists of a succession of (apparent) random steps — although, in reality, the path may not be truly random.
This new quantum walk model does not depend upon the active control of qubits, and, according to the researchers, any computational error can be made “arbitrarily small”. In principle, the model can accommodate any quantum algorithm — and may actually reveal brand new algorithms.
To elaborate on this new QC model, I offer the complete IQC press release:
The IQC team of Andrew Childs (Associate Professor of Combinatorics and Optimization), David Gosset (Post-Doctoral Fellow) and Zak Webb (PhD student) have proposed a new universal computational model. This model has the potential to become an architecture for a scalable quantum computer without the need to actively manipulate qubits during the computation.
In the paper titled Universal computation by multi-particle quantum walk (published in the February 15, 2013 issue of Science), the co-authors utilize quantum walks, the quantum mechanical analogue of classical random walks. Multi-particle quantum walk can be viewed as a collection of interacting particles that move in superposition on a graph, a structure in which pairs of vertices are connected by edges. Traditionally, quantum algorithms are implemented on a register of qubits by actively manipulating them according to a set of desired operations. In this new model, any desired quantum algorithm can be implemented by letting the qubits “quantum walk” on an appropriately chosen graph, without having to control the qubits.
Whereas many previous quantum-walk experiments have not offered scalability, the new construction offers the potential for significant quantum speedup. The team believes the model could be naturally realized in a variety of systems, including traditional nonlinear optics, neutral atoms in optical lattices and photons in arrays of superconducting qubits.
Childs notes, “Quantum walk-based computing is particularly promising due to its universality. In principle, we can cast any quantum algorithm into this model. I would love to see an experimental implementation of our construction. I’d also like to see if new quantum algorithms could be discovered within the model.”
And, quoting from the published paper’s abstract:
‘A quantum walk is a time-homogeneous quantum-mechanical process on a graph defined by analogy to classical random walk. The quantum walker is a particle that moves from a given vertex to adjacent vertices in quantum superposition. We consider a generalization to interacting systems with more than one walker, such as the Bose-Hubbard model and systems of fermions or distinguishable particles with nearest-neighbor interactions, and show that multiparticle quantum walk is capable of universal quantum computation. Our construction could, in principle, be used as an architecture for building a scalable quantum computer with no need for time-dependent control.’ *
* (source: Science, 15 February 2013: Vol. 339 no. 6121 pp. 791-794DOI:10.1126/science.1229957)
This new model allows simulation of an efficient, multi-particle quantum walk without having to conduct an actual multi-particle quantum walk (which is non-scalable). Of course, all such models have bounds (such as the time and space needed to carry out such highly complex operations). The authors acknowledge that their model is “almost certainly not optimal” but also assert that these bounds are “sufficient to establish universality with only polynomial overhead.” and that their model “exactly captures the power of quantum computation.”
Top Diagram: source: the IQC press release.
Second Diagram: Glosser.ca ; CC – By -SA 3.0