Send the link below via email or IMCopy
Present to your audienceStart 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
Big Data - A Quantum Leap
Transcript of Big Data - A Quantum Leap
A Quantum Leap
Data Universe Explosion
A New Computational Paradigm
Quantum Computing Models
Big Data Processing Problem
Since beginning of time
HAS BEEN generated
GYGABATES WORTH OF DATA
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
atoms, light, ...
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
300 digits integer
300 digits integer
Quantum Computing Today
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.
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.
Carbon Capture. - design a catalyst to more efficiently capture waste carbon, using less energy.
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 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
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.
Equation (3) shows that a qubit state can be manipulated by changing angles, a method which is in the heart for quantum computing.
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
scale of data
streaming data analysis
different forms of data
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:
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
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.
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 ...
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.
a 0 b 1
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
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
Quantum Computing Today
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
The algorithm has been tested for protein sequence search with the same speedup.
Seth Lloyd , MIT
"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.