Its Quantum Computing

Tuesday, April 10, 2012

Qbit–What it is ?

In quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom. The physical construction of a quantum computer is itself an arrangement of entangled atoms, and the qubit represents both the state memory and the state of entanglement in a system. A quantum computation is performed by initializing a system of qubits with a quantum algorithm —"initialization" here referring to some advanced physical process that puts the system into an entangled state.

The qubit is described by a quantum state in a two-state quantum-mechanical system, which is formally equivalent to a two-dimensional vector space over the complex numbers. One example of a two-state quantum system is the polarization of a single photon: here the two states are vertical polarization and horizontal polarization. In a classical system, a bit would have to be in one state or the other, but quantum mechanics allows the qubit to be in a superposition of both states at the same time, a property which is fundamental to quantum computing.

Bit versus qubit

A bit is the basic unit of computer information. Regardless of its physical realization, a bit is always understood to be either a 0 or a 1. An analogy to this is a light switch— with the off position representing 0 and the on position representing 1.

A qubit has some similarities to a classical bit, but is overall very different. Like a bit, a qubit can have two possible values—normally a 0 or a 1. The difference is that whereas a bit must be either 0 or 1, a qubit can be 0, 1, or a superposition of both.

Representation

The two states in which a qubit may be measured are known as basis states (or basis vectors). As is the tradition with any sort of quantum states, Dirac, or bra-ket notation, is used to represent them. This means that the two computational basis states are conventionally written as $| 0 \rangle$ and $| 1 \rangle$ (pronounced "ket 0" and "ket 1").

Qubit states

Bloch sphere representation of a qubit. The probability amplitudes in the text are given by $\alpha = \cos\left(\frac{\theta}{2}\right)$ and $\beta = e^{i \phi} \sin\left(\frac{\theta}{2}\right)$ .

A pure qubit state is a linear superposition of the basis states. This means that the qubit can be represented as a linear combination of $|0 \rangle$ and $|1 \rangle$ :

$| \psi \rangle = \alpha |0 \rangle + \beta |1 \rangle,\,$

where α and β are probability amplitudes and can in general both be complex numbers.

When we measure this qubit in the standard basis, the probability of outcome $|0 \rangle$ is $| \alpha |^2$ and the probability of outcome $|1 \rangle$ is $| \beta |^2$ . Because the absolute squares of the amplitudes equate to probabilities, it follows that α and β must be constrained by the equation

$| \alpha |^2 + | \beta |^2 = 1 \,$

simply because this ensures you must measure either one state or the other.

Bloch Sphere

The possible states for a single qubit can be visualised using a Bloch sphere (see diagram). Represented on such a sphere, a classical bit could only be at the "North Pole" or the "South Pole", in the locations where $|0 \rangle$ and $|1 \rangle$ 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 \rangle +i|1 \rangle}\over{\sqrt{2}}$ would lie on the equator of the sphere, on the positive y axis.

The surface of the sphere is two-dimensional space, which represents the state space of the pure qubit states. This state space has two local degrees of freedom. It might at first sight seem that there should be four degrees of freedom, as α and β are complex numbers with two degrees of freedom each. However, one degree of freedom is removed by the constraint $| \alpha |^2 + | \beta |^2 = 1 \,$ . Another, the overall phase of the state, has no physically observable consequences, so we can arbitrarily choose α to be real, leaving just two degrees of freedom.

It is possible to put the qubit in a mixed state, a statistical combination of different pure states. Mixed states can be represented by points inside the Bloch sphere.

Operations on pure qubit states

There are various kinds of physical operations that can be performed on pure qubit states.^{[citation needed]}

A quantum logic gate can operate on a qubit: mathematically speaking, the qubit undergoes a unitary transformation. Unitary transformations correspond to rotations of the Bloch sphere.
Standard basis measurement is an operation in which information is gained about the state of the qubit. The result of the measurement will be either $| 0 \rangle$ , with probability $|\alpha|^2$ , or $| 1 \rangle$ , with probability $|\beta|^2$ . Measurement of the state of the qubit alters the values of α and β. For instance, if the result of the measurement is $| 0 \rangle$ , α is changed to 1 (up to phase) and β is changed to 0. Note that a measurement of a qubit state entangled with another quantum system transforms a pure state into a mixed state.

Entanglement

An important distinguishing feature between a qubit and a classical bit is that multiple qubits can exhibit quantum entanglement. Entanglement is a nonlocal property that allows a set of qubits to express higher correlation than is possible in classical systems. Take, for example, two entangled qubits in the Bell state

$\frac{1}{\sqrt{2}} (|00\rangle + |11\rangle).$

In this state, called an equal superposition, there are equal probabilities of measuring either $|00\rangle$ or $|11\rangle$ , as $|1/\sqrt{2}|^2 = 1/2$ .

Imagine that these two entangled qubits are separated, with one each given to Alice and Bob. Alice makes a measurement of her qubit, obtaining—with equal probabilities—either $|0\rangle$ or $|1\rangle$ . Because of the qubits' entanglement, Bob must now get exactly the same measurement as Alice; i.e., if she measures a $|0\rangle$ , Bob must measure the same, as $|00\rangle$ is the only state where Alice's qubit is a $|0\rangle$ .

Entanglement also allows multiple states (such as the Bell state mentioned above) to be acted on simultaneously, unlike classical bits that can only have one value at a time. Entanglement is a necessary ingredient of any quantum computation that cannot be done efficiently on a classical computer.

Many of the successes of quantum computation and communication, such as quantum teleportation and superdense coding, make use of entanglement, suggesting that entanglement is a resource that is unique to quantum computation.

Quantum register

A number of entangled qubits taken together is a qubit register. Quantum computers perform calculations by manipulating qubits within a register. A qubyte is a collection of eightentangled qubits. It was first demonstrated by a team at the Institute of Quantum Optics and Quantum Information at the University of Innsbruck in Austria in December 2005.

Variations of the qubit

Similar to the qubit, a qutrit is a unit of quantum information in a 3-level quantum system. This is analogous to the unit of classical information trit. The term "qudit" is used to denote a unit of quantum information in a d-level quantum system. A quiet qubit refers to a qubit that can be efficiently decoupled from the environment.

Physical representation

Any two-level system can be used as a qubit. Multilevel systems can be used as well, if they possess two states that can be effectively decoupled from the rest (e.g., ground state and first excited state of a nonlinear oscillator). There are various proposals. Several physical implementations which approximate two-level systems to various degrees were successfully realized. Similarly to a classical bit where the state of a transistor in a processor, the magnetization of a surface in a hard disk and the presence of current in a cable can all be used to represent bits in the same computer, an eventual quantum computer is likely to use various combinations of qubits in its design.

Part of a series on "Quantum computing for the determined".

Qubit storage

In a paper entitled: "Solid-state quantum memory using the ³¹P nuclear spin," published in the October 23, 2008 issue of the journal Nature,an international team of scientists that included researchers with the U.S. Department of Energy's Lawrence Berkeley National Laboratory (Berkeley Lab) reported the first relatively long (1.75 seconds) and coherent transfer of a superposition state in an electron spin "processing" qubit to a nuclear spin "memory" qubit. This event can be considered the first relatively consistent quantum Data storage, a vital step towards the development of quantum computing.

Origin of the concept and term

The concept of the qubit was unknowingly introduced by Stephen Wiesner in 1983, in his proposal for unforgeable quantum money, which he had tried to publish for over a decade.

The coining of the term "qubit" is attributed to Benjamin Schumacher. In the acknowledgments of his paper, Schumacher states that the term qubit was invented in jest (due to its phonological resemblance with an ancient unit of length called cubit), during a conversation with William Wootters. The paper describes a way of compressing states emitted by a quantum source of information so that they require fewer physical resources to store. This procedure is now known as Schumacher compression.

Saturday, August 28, 2010

Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers

Abstract:
We consider the possibility of adding noise to a quantum circuit to make it efficiently simulatable classically. In previous works this approach has been used to derive upper bounds to fault tolerance thresholds - usually by identifying a privileged resource, such as an entangling gate or a non-Clifford operation, and then deriving the noise levels required to make it `unprivileged'. In this work we consider extensions of this approach where noise is added to Clifford gates too, and then `commuted' around until it concentrates on attacking the non-Clifford resource. While commuting noise around is not always straightforward, we find that easy instances can be identified in popular fault tolerance proposals, thereby enabling sharper upper bounds to be derived in these cases. For instance we find that if we take Knill's high threshold proposal together with the ability to prepare any possible state in the $XY$ plane of the Bloch sphere, then no more than 3.69% error-per-gate noise is sufficient to make it classical, and 13.71% of Knill's gamma noise model is sufficient. These bounds have been derived without noise being added to the decoding parts of the circuits. Introducing such noise in a toy example suggests that the present approach can be optimised further to yield tighter bounds.

Friday, August 27, 2010

Quantum Algorithms A Different View

A view of quantum algorithms via linear algebra

David Hilbert is famous, beyond famous. He is one of the greatest mathematicians of all time. I wish to quote him on theories:

A mathematical theory is not to be considered complete until you have made it so clear that you can explain it to the first man whom you meet on the street.

Algorithms Not Physics

My goal was to remove QA’s from any physical considerations. If this offends the quantum experts, then I am sorry. No I am not sorry. I think we need to do this to make progress.

We have done this decoupling almost completely with classical algorithms. When we explain a new classical algorithm we talk about high level operations—we do not talk about transistors and wires. Nor gates and memory cells. I would venture that few theorists could explain the details of how an L2 cache works, or how a modern arithmetic unit does pipelining, or in general how processors really work. The beautiful point is, it just does not matter for most of theory.

It is this ability to think at a high level for the creation and analysis of classical algorithms that, I believe, is the reason theory has been able to create such powerful algorithms. These algorithms are often described at a level way above any implementation details. I believe this is fundamental, and one of the cornerstones of why theory works.

Here are two classical algorithms: RSA Encryption and the Number Field Sieve (NFS). Both have changed the world, and were on Dick Karp’s list at the last Theory Day at Tech as great algorithms. Neither is described at a low level. For example, RSA is usually described in terms of operations on large integers—each of these operations requires millions of binary operations to perform. NFS is described also at a very high level. Without this ability I doubt that either algorithm would have been discovered.

I think that to make radical progress on QA’s we need to move away from a bit-level understanding and analysis and move to a high-level understanding. This is what I tried to supply in the previous post on quantum algorithms. If I failed in that goal, I apologize to you, but I believe that this goal is the right one. Perhaps someone else will be able to succeed in raising the level of detail—I hope so.

Geometry Not Quantum Mechanics

In that previous discussion I tried to make the assumptions needed to understand the Deutsch algorithm as simple as possible. This was to help a non-expert to “see” what was happening without any quantum mechanics details. I also believe that by stripping away tensor products, qubits, Hadamard Transforms, and all the rest we could lay bare what is really happening. I agree that none of these concepts are too difficult, but are they essential to make a person have a “feel” for what is happening with QA’s? I do not believe that they are.

I also hope that this view can be used by theory experts to make further progress on QA’s. If the details are pushed aside and all that is left is a simple question about unit vectors on the sphere, then I hope that we might be able to find new insights. I am working right now on doing this, and I believe that I may succeed. If QA are “just” questions about geometry, then I assert that we may be able to find new QA’s or prove new lower bounds. I still believe that is true.

Grover’s Algorithm

Lov Grover discovered one of the most important QA known in 1996. Or is that “invented?” The algorithm named after him is able to search a space of size ${N}$ in cost ${O(\sqrt N)}$ . Of course, this is much faster than any classical algorithm, which would take linear time, even for random algorithms.

Grover’s beautiful result has many applications. You can think of his algorithm as allowing the computation of an ${N}$ sized “OR” in time square root of ${N}$ . This is so general that it has had many applications in various areas of complexity. For example, it can be used to perform triangle detection faster than any known classical method—see the beautiful paper by Frederic Magniez, Miklos Santha, and Mario Szegedy.

It should be noted in this and many other applications there are nice interactions between Grover and standard methods. That is, the optimal results often follow from a “clever” use of Grover’s algorithm.

The Linear Algebra View

Let me explain Grover’s algorithm using just linear algebra. We begin in a state ${s}$ of not knowing anything about the space of possible solutions— ${s}$ is the all- ${1}$ vector, but divided by ${\sqrt{N}}$ to make it a unit vector. Let us suppose there are ${k}$ solutions. We do not know ${k}$ in advance. However, we will argue that it is enough to know ${k}$ to within a factor of ${2}$ . Then we will apply the standard idea of first trying ${k = N/2}$ , then ${k = N/4}$ , then ${k = N/8}$ and so on, and this will not affect the order of the running time. So we may suppose ${k}$ is known after all—and what we really do not know is the location ${R \subseteq [N]}$ of the solutions. Our goal state is the vector ${1_R}$ that has a ${1}$ in those positions that belong to ${R}$ , and ${0}$ elsewhere, this time dividing by ${\sqrt{k}}$ to make a unit vector ${r = 1_R/\sqrt{k}}$ .

All states ${q}$ that we reach along the way will be linear combinations of our initial ignorance state ${s}$ and the unknown full-knowledge state ${r}$ , that is

$\displaystyle q = as + br$

where ${|a|^2 + |b|^2 = 1}$ to preserve a unit vector. Initially we have ${a = 1}$ , ${b = 0}$ . When we measure, the chance of getting the index of a solution is ${|a|^2(k/N) + |b|^2}$ . Initially this is just ${k/N}$ , which is just the chance of guessing a solution at random. If ${|b|}$ is high, however, then we stand a good chance of getting a solution. So that’s the goal of Grover’s algorithm—to stay in the simple two-dimensional subspace ${S}$ spanned by ${s}$ and ${r}$ , while moving from ${s}$ close enough to ${r}$ for a measurement to give a solution with high probability. We just need some operations that keep this subspace fixed but move points well enough inside it.

The first operation is an ${N}$ by ${N}$ matrix ${A}$ that is the identity matrix—except that the diagonal entries corresponding to solutions are ${-1}$ instead of ${1}$ . That is, ${A = I - 2\mathrm{diag}(1_R)}$ . This matrix is given as a “black box”—we are not allowed to inspect it. It really represents the verification predicate that an element is a solution. Since ${A^2 = I}$ , clearly ${A}$ is unitary. The second operation is simply the matrix

$\displaystyle B = \frac{2}{N}J - I$

where ${J}$ is the all ${1}$ matrix. Each row has one entry of ${(2/N) - 1}$ and ${(N-1)}$ entries of ${2/N}$ . Its norm is therefore

$\displaystyle (\frac{2}{N} - 1)^2 + (N-1)(\frac{2}{N})^2 = \frac{4}{N^2} - \frac{4}{N} + 1 + \frac{4}{N} - \frac{4}{N^2} = 1.$

All pairs of different rows have dot product ${2(2/N - 1)(2/N) + (N-2)(2/N)^2 = 8/N^2 - 4/N + 4/N - 8/N^2 = 0}$ . So ${B}$ is also a unitary matrix. To verify that these operations conserve the subspace ${S}$ , note that ${Js = Ns}$ while ${Jr = ks/\sqrt{k} = \sqrt{k}s}$ , and compute:

$\displaystyle \begin{array}{rcl} As &=& (I - 2\mathrm{diag}(1_R))s = s - 2\sqrt{\frac{k}{N}}r \\ Ar &=& -r \\ Bs &=& \frac{2}{N}Js - s = 2s - s = s \\ Br &=& \frac{2}{N}Jr - r = 2\sqrt{\frac{k}{N}}s - r. \end{array}$

The algorithm then simply computes

$\displaystyle q = (BA)^m s,$

where ${m \approx \sqrt{N/k}}$ . Then, it measures the vector ${q}$ . The claim is with high probability the measurement yields some index ${i}$ so that ${A_{ii}=-1}$ .

Grover Analysis

The key here is to prove that the algorithm works: that is after applying the matrix ${BA}$ about square root of ${N}$ times the measurement yields a solution with high probability. Given our insight about preserving a two-dimensional subspace, this comes down to simple linear algebra on ${2 \times 2}$ matrices. The algebra is the same as on Wikipedia’s page on Grover’s algorithm for the case ${k = 1}$ , except we replace factors ${\sqrt{1/N}}$ by ${\sqrt{k/N}}$ .

We can see intuitively from the above action of ${A}$ and ${B}$ on ${s}$ and ${r}$ that ${BA}$ effects a rotation through an angle of ${\mathrm{arcsin}(2\sqrt{k/N})}$ , which is roughly ${2\sqrt{k/N}}$ when ${k}$ is small relative to ${N}$ . Starting from ${s}$ which is the point ${(1,0)}$ in this co-ordinate system, it takes about ${(\pi/2)(\sqrt{N/k}/2) = (\pi/4)\sqrt{N/k}}$ iterations to get near the point ${(0,1)}$ . We get near within distance about ${\sqrt{k/N}}$ , in fact, and the error when measuring is hence order-of the square of that, i.e. only order ${k/N}$ . Note that as it iterates, the algorithm gets progressively closer to its goal—in the sense that if “Simon says: measure” at any time, its chance of finding a solution always improves.

Finally, as we noted above, if we do not know ${k}$ then we make a “net” by guessing ${k = N/2}$ then ${k = N/4}$ then ${k = N/8}$ and so on. When our “ ${k}$ ” is off by a factor of 2 we will not get so near to the point ${(0,1)}$ . However, there will be multiple iterations for values ${k}$ in our net that are close enough to give a reasonable success probability. The full analysis involves a tradeoff between random guessing working well when ${k}$ is large, versus the error ${k/N}$ being small when ${k}$ is small, and repeating some measurement trials to make the net a little finer than stepping down by factors of ${2}$ . The details need to be worked out, but these details are not quantum mechanical—they are ordinary theory-of-algorithms details.

Open Problems

The goal here was not to supplant the current view of QA’s. Nor was it to not teach all the details to our students. The goal was both less and more important. It was to start to try to create a way to look at QA’s that was simpler, more accessible to many. And at the same time could lead us to discover new insights into QA’s. I believe that the more ways we can define and view a mathematical topic, the better is our understanding.

I hope that I helped in this regard. In any event thanks to all who read that discussion and this one. Thanks for being supportive—even those who disagree with this approach.

Pages