bb68 Quantum computer - Telecomix Crypto Munitions Bureau

Quantum computer

From Telecomix Crypto Munitions Bureau

Jump to: navigation, search

DISCLAIMER: This article is 100% random and mostly just is about trying to figure out how the quantum computers will work, if they work. By using publicly available sources and a book i found in my campus book shop, it seems to be possible.

THIS ARTICLE NEEDS A LOT MORE ACTUAL CODE. it just covers the absolute basics atm.

Contents

[edit] Papers and other sources

Related and severely interesting

[edit] Why?

  • Because quantum computers already exist. (Yes, they can currently only hold a few qubits. But that will change, I think!)
  • Because they will likely become a real thing within my lifetime.
  • And also because i want to understand what type of computations that makes up the next layer of this reality.

[edit] What?

This science is in its cradle: Just like programming ordinary computers once upon a time required a PhD in electronics, so does programming quantum computers today require a PhD in quantum physics. There are almost no papers written that does not assume that the reader is really good at math and physics.

I want to change that.

I think it is possible to demystify quantum computing in order to make it possible for ordinary humans (like myself) to program them. This is pretty much what this article is all about :)

Assumptions:

  1. Quantum computers are not magical.
  2. Quantum computers are possible to program without a deep understanding of quantum physics.

If you want to learn quantum physics, you should not continue reading. This article is only about how to program quantum computers.

[edit] Tools

QCL is a programming language and an command line-interpreter that can be used to experiment with a model of a quantum computer. You can download it here. It seems to be the easiest and most researched quantum programming language around.

QCL can emulate small quantum computers. The emulator can break the laws of physics since it is just a representation of a quantum computer. Therefore it is possible to peek at qubits without destroying their superpositions, something which is not possible in the real world. Emulation also means that it takes a lot longer to finish large computations than it would if we actually had access to a real quantum computer, but if we limit the emulator to using just a few qubits, we will not notice the lag. (Do not try to run shor's algorithm on numbers larger than ~250.)

There is also a quantum-dialect of brainfuck :D

[edit] Introduction

  1. Quantum probability
  2. Superpositions
  3. Entanglement
  4. Decoherence
  5. How to make computations

It is difficult to describe any of the concepts without referring to any of the other concepts. This means that you might need to re-read some parts twice.

Ok, here we go...

[edit] Quantum probability

First, we examine real world probability. Then we go from there in order to describe quantum probability :)

[edit] Ordinary probability

If we flip a coin, the probability that it results in a head is 0.5. We write this as 

P(head) = P(tail) = 0.5

and 

P(head) + P(tail) = 1

If we are throwing two coins at the same moment, the probability that their positions ends up as tail-tail is P(tail)*P(tail) = 0.25.

If we flip two coins at the same time, we can not make them affect each others results. Their results are always independent of each others (unless we cheat).

[edit] Quantum probability

If we have a quantum-coin (a qubit) we end up with this equation (compare with the above one!): 

|P(head)|^2 + |P(tail)|^2 = 1

We can flip two quantum-coins and have them affect each others results. (This is called entanglement, and it is how we cheat.)

The four different positions we can end up with is 

P(head, head) = A
P(head, tail) = B
P(tail, head) = C
P(tail, tail) = D

And 

|A|^2 + |B|^2 + |C|^2 + |D|^2 = 1

If P(head) > P(tail), this means that there is a much higher probability that A (that is, head-head) becomes the result, because the probabilities are squared.

With two entangled qubits, we end up with a four possible outcomes (A, B, C or D). With three entangled qubits, we will have eight possible outcomes. With a hundred entangled qubits, the quantum computer will be able to "select" one out of 2^100 = 1.27 * 10^30 outcomes. Selection occurs when the qubits leave their superpositions due to decoherence.

Since the probability of each single outcome is squared, it means that a single outcome can be made to have a much higher possibility of ending up as the answer than any other possibility. It is possible to use this property to find solutions to problems that are difficult to find via other means. Programs for quantum computers will use this to "guide" the computer towards the correct solution.

Notice that it is not possible to completely remove the possibility of the other, erroneous solutions. This means that quantum computers can never come up with the correct answer with a 100% probability. This is not a problem, we will just re-run the quantum program until we know we found the answer.

[edit] Superposition

Bits can be in either two states: Zero or One.

Qubits can be in more states. They can be Zero, One or in a superposition. Superpositions are described using quantum probabilities. A qubit in a superposition does not have a value until decoherence occurs. Multiple qubits may be in the same superposition, if they are entangled.

[edit] Entanglement

Entanglement is when more than one qubit is in the same superposition. They are "glued together", or entangled. Two qubits can be said to make up a 2-bit quantum processor register if they are entangled with each other.

Qubits that are entangled with each others does not have to be in physical proximity of each others.

A single qubit can only return the answer yes or no, after it has been measured, and has little benefit over a traditional one-bit electronic computer. If thirty qubits are entangled with each other however, they can be made to appear as if they are making 2^30 = 1073741824 computations at the same time. (A single qubit may only collapse into two states: one or zero. 30 entangled qubits may collapse into any of about roughly one billion different states.)

When qubits are entangled in the same superposition, it basically just means that we do not yet know what state the qubits are in. For example, two qubits could together be in 00 or 11 (the bell state). If one then measures only the first of the twoqubits, a measurement on the second qubit will result in the same value as the first. (We have two qubits: xx, and then measures the first so that we have 1x. Then, because we know the two qubits are entangled in the same superposition and the only alternatives for their combined value is either 00 or 11, then we know that the 2nd qubit will also be a 1.)

Entanglement can not be used to transmit information faster than the speed of light. It would be possible to transmit information faster than the speed of light if one could select the outcome of a measurement, but this is not the case. One can think of the shared superposition as if the qubits already have established a common state, but that this state has not been revealed to the outside world. (Weird example: This is a bit like having a magical gnome (quantum computer) write down the same number (entanglement) on two different pieces of paper (two qubits), and then storing the papers without looking at them (two qubits in the same superposition). When you eventually look at the paper (measurement), you know that the same number is written on the other piece of paper too. No information is transmitted between the two papers, they already had their values written on them = It is not possible to transmit information faster than the speed of light using entanglement.)

[edit] Decoherence

Decoherence is that a variable in a superposition is given a value. (This is what happens to Schrödingers Cat when we open the box to check if its alive or not.)

When the state of a qubit is measured, decoherence occurs. The qubit is given a value.

Before decoherence occurs, the values of qubits can only be described using quantum probabilities.

Controlled decoherence occurs after we are done with the computations, at the same instant we measure the result.

Uncontrolled decoherence occurs when the causality of the external world leaks into the machine and fucks up the superpositions of our qubits. This results in that the wrong answer is returned from the quantum computer. Uncontrolled decoherence is a very big problem for real-world quantum computers.

[edit] How to make computations

[edit] Risk of errors

Two big sources of errors:

  1. The risk of uncontrolled quantum decoherence means that the quantum computer could just fail to return a correct answer, because the machine collapsed back to real world causality before the calculations were complete.
  2. Quantum probability means that a program only returns a probable answer. (BQP assumes the error rate is below 1/3.)

This means that we need to use an ordinary computer to check if the answer the quantum computer gave us is indeed correct. (Or, if that is impossible due to the nature of the problem, run the same quantum program over and over again to collect statistics, and then make a qualified guess.)

In the picture above

  • Classical control structure = ordinary computer
  • Unitary transformation = operations on quantum registers are described with unitary matrices. These matrices are called "gates". Think of them as ordinary logic gates, except that they operate on vectors.
  • measure machine state = controlled decoherence

Example: (Please occasionally do look at the picture above while reading this.) Say that we wish to factorize a large number. This takes a lot of time using ordinary electronic computers, but can be done in an instant using a quantum computer. Since it takes much less time to multiply numbers than to find the prime factors of a number using an oldskool computer, we instead use the quantum computer to find a set of probable factors. When the quantum computer has reached an answer, we proceed to use an ordinary computer to multiply the factors that the quantum computer gave us, to check if they result in the number we wished to factorize. If not, we just simply restart the procedure and try again. (It is easy to multiply numbers using ordinary computer, and it is easy to factorize numbers using quantum computers. They complement each others.)

Notes:

  • Shors algorithm is used to factorize numbers on quantum computers. You can find the QCL source code here.
  • Algorithms often belong to the BPQ complexity class.

[edit] Stuff worth to know

Notes about quantum registers

  • Registers are allocated by the number of qubits they need to contain. See QCL examples below.
  • A single-bit register is a two dimensional vector in the complex plane.
    • |0> and |1> are the base vectors. When the vector is aligned to any of these, it can be thought and handled like a classic bit.
    • When it is in a superposition, the one-bit register is a vector that holds the property |A|0>|^2 + |B|1>|^2 = 1, where A and B are the amplitudes of the states. Red vertical bars means absolute value. Amplitudes are real numbers that may be negative. The registers unmeasured value can be thought of as a point on the surface of a unit sphere.
  • The probability that a quantum register will collapse into any of its different states is related to the states amplitude, squared. Therefore it does not matter if the amplitudes are negative.
  • Multi-bit quantum registers are vectors in the 2^n complex space, where n is the number of qubits in the register. (Thus, for example, a "qubyte" is a 256-dimensional complex vector.)
    • When not in superposition, the vector is aligned to the base vectors. Example |0110> is a 4-bit register not in superposition. |0110> can be thought of as equal to the classic 0110 bitstring.
    • When in superposition, the n-bit register also holds the property that the sum of each one of its amplitudes squared equals 1. (The probability of all possibilities may not be anything but 100%, that is; 1.)
    • The difference between n-bit registers and 1-bit registers in superpositions is that n-bit registers will have 2^n different states to collapse into, instead of just 2^1=2 states. A three-bit register can collapse to 000, 001, 010, 011, 100, 101, 110 and 111. In QCL it will look something like this: |A|000>|^2 + |B|001>|^2 + |C|010>|^2 + ... + |H|111>|^2 = 1, where A, B, C ... H are yet again real numbers.

Notes about gates

  • Every gate is a unitary matrix. There are a bunch of gates (think of the matrices as equivalent to NOT, XOR, AND, etc) that we can use, without having to define the matrices ourselves.
  • Quantum computers can not erase the results of computations while performing operations on registers in superpositions. This is known as reversible computing. Paraphernalia knowledge: This is because all operations consume absolutely no energy, and bit erasure evaporates energy. In classical computers, bit erasure means that the voltage over at least one transistor disappears and heat is generated as a result from that. Measurement also involves the release of entropy, since it is not possible to observe something without affecting the measured object (heisenbergs uncertainty). Irreversibility is closely related to the passage of time, the reversible nature of quantum computers can be interpreted as the concept of time does not exist during a computation. There is no such thing as "event A happened before event B" until the computation is complete and the waveform collapses (waveform collapse is another word for decoherence). This does not mean that the quantum computer is a perpetual motion machine, it requires energy to create an environment without spontaneous decoherence. It seems to be physically impossible to create perpetual quantum computers, the background radiation from the Big Bang sets the limit. For more on this topic, read The Physics of Information Processing Superobjects: Daily Life Among the Jupiter Brains.
  • It is possible to approximate the erasure of the results of computations if the programmer (or compiler) stores enough information for being able to reversing them. One however does not have to reverse the computations, they just needs to be possible to reverse. This is often done by storing "control bits". Many of the gates makes use of control bits, if they are not inherently reversible.
  • Typical gates are
    • CNOT -- Controlled NOT, two input bits, one control bit and one target bit. If the control bit is set, then a classic NOT operation is performed on the target bit.
    • CPhase -- Controlled phase shift. It also has control and target bit.
    • X, Y and Z pauli matrices -- Basic operations that feel somewhat like the equivalents of NOT, but they flips vectors upside down, inside out, etc. instead of just inverting, as NOT would do.
    • Hadamard -- Called Mix() in QCL. Usually just used to move a register into a superposition.
    • QFT -- the quantum fourier transform can be a single gate. This gate can be constructed out of a series of CNOT and CPhase gates. It can be optimized by using butterflies. The QFT is used in Shors algorithm, it is defined as a function taking two qureg (quantum register) values.

More that is nice to know more about: Bell state, superdense coding, quantum teleportation. (use wikipedia, or contribute to this article if you know.)

[edit] More random notes

an n-qubit register can be described as either

  • a vector in C^(2^n). C is the complex numbers. So, a single cubit is a vector in C^2. A qubyte is a vector in C^256. Because i^2 = -1, vectors with negative depths (depth = absolute value) is allowed in these dimensions.
  • a 2^n long string of probabilities that the vector will collapse to either one of its base vectors, when measured. One probability for each base vector. (The bra-ket notation.)

The base vectors represent the binary numbers that the register can assume at the instant of measurement (decoherence). There are 2^n dimensions because there are 2^n different probability that a register collapses to each one of the base vectors. The probability is related to the absolute value of "how deep within that dimension the vector is." (its amplitude in that dimension.)

Since each dimension has both one real and one imaginary part, the depth is equal to the square root of the real part squared plus the imaginary part squared (pythagoras). This is written as the absolute value.

The absolute value is the aplitude, the probability that the register will collapse to a certain value when measured (the vector aligns itself with one of its 2^n base vectors.)

A vector always have the length one, since the total sum of all probabilities (its sum of its depths in each one of its dimensions) can never become anything but 100%.

Input data is delivered as vectors aligned to one of their base vectors. AKA, bitstrings. Then the QC multiplies the vectors with a series of unitary matrices (which can be thought of as rotating the vectors, or as performing transforms on the series of complex numbers that describes the measurement probabilities.) A program is defined as a sequence of unitary matrices ("gates", just like classical computers. same same, but different..). When the program has come to its end, the QC measures the register, decoherence occurs, the register aligns with one of its base vectors and becomes a bitstring. This bitstring is then fed into the classical computer.

...i has no idea how to make useful computations within this framework. i has to study moar :)

[edit] Programming your quantum computer

This contain errors. Please correct them yourself.

All operations in a quantum computer consists of applying unitary matrices to the quantum-registers. Each quantum register contains an array of "probability vectors" (the superpositions are represented that way). When we apply the matrices, the probability vectors change.

Quantum computation is a bit like manipulating the cube in hellraiser. Every operation is a unitary matrix that, when applied, "rotates" (changes) the "object" (probability vectors) slightly.

Also, most of the time we do not have to care about the matrices. Many of the important ones are pre-programmed.

Get QCL up and running!

  1. download (if down: Archive.org) the binary distribution of QCL and unzip it.
  2. Goto the path where you downloaded it and run it (requires linux)

Allocate 5 qubits from the quantum heap... 

./qcl --bits=5
QCL Quantum Computation Language (5 qubits, seed 1316456645)
[0/5] 1 |0>

Obtain a 2-qubit entangled superposition register 

qcl> qureg a[2];
qcl> dump a;
: SPECTRUM a: <0,1>
1 |0>
qcl> Mix(a);
[2/5] 0.5 |0> + 0.5 |1> + 0.5 |2> + 0.5 |3>
qcl> dump a;
: SPECTRUM a: <0,1>
0.25 |0>, 0.25 |1>, 0.25 |2>, 0.25 |3>
qcl>

What happened? The Hadamard function, named Mix() here, puts the qubits in a superposition. There is nothing special with Hadamards function, a lot of functions does this. Hadamard probably is the cleanest method to reach a superposition though. After the Mix(a) is executed, the number of qubits allocated (2 out of 5) is displayed, along with he probability of any given outcome. 0.5 actually means 0.25, but the square is not calculated (this is because the probability could be negative, and when a negative number is squared it becomes positive. We do not wish to lose that information.)

If one dumps the register (not possible outside the simulator - it would break the superposition if you looked at it) it says that there is a 0.25 chance of any of the four outcomes. Two qubits can collapse into any of 00, 01, 10 and 11. For example, "0.25 |3>" means that there is a 0.25 chance that 11 is the answer, if we would let the superposition collapse at this moment.

Continuing the QCL session from above.. 

qcl> measure a;
[2/5] 1 |3>

Read as: The probability is 1 that we have a 3 (binary 11) in the register.

When we measure the quantum register a, we have controlled decoherence, and the register obtains a single value. In this case, binary 11, or decimal 3. The answer could just as well have been 2, 1 or 0.

This IBM tutorial contains an example of some über-awesome parallelism that shows the power of quantum computing :) To be honest, i just read it and..

[edit] Next step?

  • Get more free time to spend on this
  • Write more complex programs.
  • Re-write the introduction and make it more accurate.
  • Have a look at the unitary matrices themselves. Describe them.
  • Also try and learn QML: a functional quantum programming language
  • Quantum Hacking

[edit] Links

EXPLORE & EXPAND

Retrieved from "https://cryptoanarchy.org/wiki/Quantum_computer"
Personal tools
0