**Big Data**

A Quantum Leap

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.