Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Big Data - A Quantum Leap

Quantum computing for Big Data analytics
by

Aleksandar Radovanovic

on 12 March 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Big Data - A Quantum Leap

Big Data
A Quantum Leap

Data Universe Explosion
Quantum Computing
A New Computational Paradigm
Big Data
Quantum Computing Models
Big Data Processing Problem
Aleksandar Radovanovic
Since beginning of time
until 2003
HAS BEEN generated
GYGABATES WORTH OF DATA
5 BILLION
today, we generate that amount of data
every few minutes
The term “Big Data,” was probably first used by John Mashey at lunch-table conversations at Silicon Graphics in the mid 1990s.
In 1981 Nobel Prize winner Richard Feynman challenged scientists to develop a computer based on quantum physics.
QUANTUM BITS (QUBITS)
the ability to be in multiple
states at one time
QUBITS ON A CHIP
superconductors,
atoms, light, ...
QUANTUM COMPUTER
Adiabatic
Circuit
Topological
Every possible solution is represented as an altitude of a landscape. The aim is to find the lowest point on the map.
Classical computers can only walk over this landscape.
Quantum computers can tunnel through the landscape
.
Similar to classical computing.
The computation is done by applying a succession of quantum logic gates that manipulate quantum bits .
Any computation can be done using combinations of these gates.
Based on In the mathematical field of knot theory.
Quasiparticles called anyons move through space/time forming imaginary braids.
These braids form quantum bits and logic gates that make up the computer.
Power of Quantum Computing
14728 ...3
14728 ...3
300 digits integer
prime factorization
Classical computer
Quantum computer
2016-01-07
22:00:00
2016-01-07
22:00:01
102,016-01-07
22:00:00
//
//
300 digits integer
primer factorization
Quantum Computing Today
Adiabatic
Circuit
Topological
D-Wave 2X - the only commercial QC (2015)
Not an universal computer - solves optimization problems.
Google's test in finding a minimum of 1000 binary variables function is 100 million times faster than a single core computer.
UNSW in Australia have designed a 3-D silicon chip architecture based on single atom quantum bits.
The structure should be scalable to millions of qubits, required for a full-scale quantum processor.
Still theoretical.
University of California, Microsoft sponsored research..
Language-Integrated Quantum Operations or LIQUi|> a software platform for quantum computing released in 2015.
Andrea Morello, Stephanie Simmons, Juan Pablo Dehollain UNSW.
Other applications
Carbon Capture. - design a catalyst to more efficiently capture waste carbon, using less energy.
Quantum Internet?
Designing better drugs and materials.
Seth Lloyd, MIT
Even the simplest linear manipulation on a large data sets could take more operations than all the computers in the world have every performed since the very first computer was invented.
Quantum computers are perfectly suited to processing this type of data -- big arrays of big vectors.
Quantum cryptography
Quantum Unstructured Data Search
Lov Grover in 1996 published a quantum algorithm for an unstructured database search. The algorithm is now know as Grover’s algorithm.
Imagine a phone directory containing N names arranged in completely random order.
In order to find someone's phone number a classical algorithm will need to look at a minimum of N/2 names.
Quantum computer can simultaneously examine multiple names.

As a result, the desired phone number can be obtained in N steps.
e.g. 1,000,000 vs. 1,000 steps
Basic buliding block of Quantum Computer - Qubit
A qubit, short for quantum bit, is the basic building block of quantum computers.
A qubit can be made of any quantum object like an electron which has two distinguishable states.
Using a branch of mathematics called linear algebra, it is possible to describe state of superposition.
Think of a classical bit as a coin. It can be either heads or tails, representing 0 or 1
Bloch Sphere
Operations on a qubit during quantum computation are equivalent to moving a point that represent the qubit around the Bloch sphere. The qubit on the picture is 80% head (1) and 20% tail (1).
A qubit in a superposition of states can be visualized as a point on a sphere.
This sphere, called Bloch sphere, has values 0 and 1 at the sphere poles.
An attempt to read the qubit value breaks the superposition and like a spinning coin, the qubit collapses to either 0 (with 80% chance) or to 1 (with 20% chance).
In other words, quantum computation ends with probabilistic, often incorrect results.
Think of a quantum bit as a constantly spinning coin. It represents heads and tails, 0 and 1 simultaneously.
This state is called superposition.
Generalized Qubit
Equation (3) shows that a qubit state can be manipulated by changing angles, a method which is in the heart for quantum computing.
Quantum Register
In general:
Classical register: one N-bit number
Quantum: 2 (all possible) N-bit numbers
300 qubits can handle amount of numbers larger than the number of atoms in the universe

The entanglement, and the scaling that results, is the key to the power of quantum computing.
What is Big Data
Big Data are data sets so large or complex that traditional data processing applications are inadequate.
4Vs of Big Data
Volume
scale of data
Velocity
streaming data analysis
Variety
different forms of data
Veracity
data uncertainty
A collection of two or more qubits is called a quantum register. Qubits inside the quantum register are acting not as two separate objects but as one coherent unit in a state called an entanglement.
A quantum register of three qubits can store individual numbers such as 3 or 7:
but, it can also store the two of them simultaneously.
We take the first qubit, prepare a superposition and get:
N
Quantum Algorithm
classical algorithm
variables
operators
workflow
quantum algorithm
Quantum algorithms are based on series of matrix (rectangular array of numbers) transformations:

initialize quantum register and bring it into superposition

in each step multiply this vector by a matrix

read the register
quantum registers
matrices
Quantum Operators
A
B
example: matrix multiplication
A x B x
|ψ⟩ = |φ⟩
U|θ, φ⟩ = |θ′, φ′⟩
Quantum operators (matrices) can be implemented as quantum gates, optics (mirrors, beam splitters), superconductors ...

General single-qubit transformation U is a rotation about an arbitrary axis.
NOT perform a rotation of the Bloch Sphere around the X-axis by 180 deg. It maps |0> to |1> and vice versa. Due to this nature, it is sometimes called bit-flip.
X
Grover Algorithm
Quantum NOT
Hadamard Gate
The Hadamard gate is a special transform mapping the qubit states |0> and |1> to two superposition states with 50/50 weight.
It is the combination of two rotations, 90 deg. about the y-axis followed by 180 deg. about the x-axis.
It is widely used as the first step of a quantum algorithm to work on all possible input values in parallel and then ends a quantum computation to collect data.
0 1 2 3 ...
Tar
14 15
"Spinning" Qubit
Imagine a qubit as a ball spinning "up" and "down".
We can assign value 0 to spin up and 1to spin down.
Representing a qubit state in Dirac bra-ket notatation.
1
0
0
0
1
1
column vector
ket vector
a
b
a 0 b 1
Grover Algorithm
Grover's algorithm can be described as "inverting a function".
If we have a function y = f(x), Grover's algorithm allows us to calculate x when given y.
Inverting a function is related to the searching of a database because we could come up with a function that produces y = 1 (true) if x matches a desired entry in a database, and another value of y = 0 (false) if not.
Grover Algorithm Performance
Source: Simulation And Evaluate The Performance Of Grover’s Algorithm With Respect To Classical Algorithm
Theoretical complexity
Simulated performance
Vital for quantum computing:
Quantum Machine Learning for Big Data
In supervised learning, the machine infers a conclusion based on a set of training examples.

Used for cancer detection, drug discovery...
Can we do even Better?

"Nonlinear quantum search using the Gross–Pitaevskii equation" shows quartic scaling of N
1/4
Quantum Computing Today
Machine learning
In unsupervised learning the machine tries to find hidden pattern in unlabeled data.

Used for: sequence analysis, genetic clustering ...
Quantum machine learning can provide exponential speed-ups over classical computers.
Machine learning is about manipulating and classifying large amounts of data.

The data is typically post-processed and ordered in arrays (vectors) and arrays of arrays (tensor products).

Quantum computers are good at manipulating vectors and tensor products in high-dimensional spaces.
Currently, the rate of generation of electronic data generated per year is estimated to be on the order of 10 bits. This entire data set could be represented by a quantum state using 60 bits, and the clustering analysis could be performed using a few hundred operations.

If each person on the earth's genome was sequenced and encoded on a vector (≈ 10 bits) one will need 60 qubits processor to analyze it.

Even if the number of bits to be analyzed were to expand to the entire information content of the universe within the particle horizon, O(10 ≈ 2 ) bits, in principle the data representation and analysis would be well within the capacity of a relatively small quantum computer.
Really BIG DATA
300
20
90
18
The algorithm has been tested for protein sequence search with the same speedup.
Seth Lloyd , MIT
Qubit Manipulation
"classical" coin (bit) flipping with a magnet
"quantum black-box" coin in "superposition" flipping - result is unknown until the box is open
Grover's algorithm searches for satisfying inputs to a function by creating a uniform quantum superposition of states, and then canceling out non-solutions.
Full transcript