User:Aliraghav60/sandbox

QUANTUM COMPUTING

What is quantum computing?

Quantum physics has defied logic since the atom was first studied in the early 20th century. It turns out atoms do not follow the traditional rules of physics. Quantum particles can move forward or backward in time, exist in two places at once and even “teleport.” It’s these strange behaviours that quantum computers aim to use to their advantage.

Classical computers manipulate ones and zeroes to crunch through operations, but quantum computers use quantum bits or qubits. Just like classical computers, quantum computers use ones and zeros, but qubits have a third state called “superposition” that allows them to represent a one or a zero at the same time. Instead of analysing a one or a zero sequentially, superposition allows two qubits in superposition to represent four scenarios at the same time. Therefore, the time it takes to crunch a data set is significantly reduced.

Every day we create volumes of data. In order to adequately process it all to extract meaning from it, we require much more computing power. That’s where quantum computers step in to save the day.

IMPORTANT TERMS

Quantum bits (Qubits)

A quantum bit (qubit) is the smallest unit of quantum information, which is the quantum analog of the regular computer bit, used in the field of quantum computing. A quantum bit can exist in superposition, which means that it can exist in multiple states at once. Compared to a regular bit, which can exist in one of two states, 1 or 0, the quantum bit can exist as a 1, 0 or 1 and 0 at the same time. This allows for very fast computing and the ability to do multitudes of calculations at once, theoretically.

Quantum Computer

A computer which makes use of the quantum states of subatomic particles to store information.

Universal Quantum Computer

The essence of a universal quantum computer is that it combines the full power of a classical computer with the power of a quantum computer, and enables simulation of physics, including and especially quantum mechanics. Current and near-term quantum computers tackle only the quantum portion of the full vision, leaving out all of the conceptual power of a Turing machine.

Quantum Logic Gate

A quantum gate or quantum logic gate is a rudimentary quantum circuit operating on a small number of qubits. They are the analogues for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible, unlike many classical logic gates. Some universal classical logic gates, such as the Toffoli gate, provide reversibility and can be directly mapped onto quantum logic gates. Quantum logic gates are represented by unitary matrices.

The most common quantum gates operate on spaces of one or two qubits. This means that as matrices, quantum gates can be described by 2 x 2 or 4 x 4 matrices with orthonormal rows.

Reversible Logic Gate

Reversible logic gates has ability to to reduce the power dissipation which is the main requirement in low power VLSI design. It has wide applications in low power CMOS and Optical information processing, DNA computing, quantum computation and nanotechnology. Because, energy will not be dissipated from a system as long as the system allows the reproduction of the inputs from observed outputs. Reversible logic supports the process of running the system both forward and backward. This means that reversible computations can generate inputs from outputs and can stop and go back to any point in the computation history. A circuit is said to be reversible if the input vector can be uniquely recovered from the output vector and there is a one-to-one correspondence between its input and output assignments, i.e. not only the outputs can be uniquely determined from the inputs, but also the inputs can be recovered from the outputs.

Quantum Circuits

There are difficulties associated with extending the circuit model to quantum computing: wires must preserve states, ancilla bits require preparation of qubits in initial states, fanout is not possible due to the no-cloning theorem, and all gates must be invertible. A quantum circuit is reversible. It connects reversible gates without fanout or loops, and hence has an equal number of input and output wires. This is a natural model that reflects the time reversibility of (both classical and quantum) physics at the microscopic level.

Quantum Circuit Depth

A depth- quantum circuit consists of time steps. Each time step contains one- and two-qubit gates acting on disjoint qubits.

Quantum Entanglement

Quantum entanglement is a quantum mechanical phenomenon in which the quantum states of two or more objects have to be described with reference to each other, even though the individual objects may be spatially separated.

This leads to correlations between observable physical properties of the systems.

For example, it is possible to prepare two particles in a single quantum state such that when one is observed to be spin-up, the other one will always be observed to be spin-down and vice versa, this despite the fact that it is impossible to predict, according to quantum mechanics, which set of measurements will be observed.

Quantum Decoherence

Quantum decoherence is the loss of quantum coherence. In quantum mechanics, particles such as electrons are described by a wave function, a mathematical representation of the quantum state of a system; a probabilistic interpretation of the wave function is used to explain various quantum effects. As long as there exists a definite phase relation between different states, the system is said to be coherent. Coherence is preserved under the laws of quantum physics, and this is necessary for the functioning of quantum computers. If a quantum system is perfectly isolated, it would be impossible to manipulate or investigate it. If it is not perfectly isolated, for example during a measurement, coherence is shared with the environment and appears to be lost with time, a process called quantum decoherence. As a result of this process, quantum behavior is apparently lost, just as energy appears to be lost by friction in classical mechanics.

APPLICATION OF QUANTUM COMPUTING

Machine Learning

Artificial intelligence needs to be able to pull from large datasets of image, video and text. Thankfully, there doesn’t seem to be a shortage of content. In fact, there may be an overabundance. Big data is out there to be analyzed, but we need more powerful computers to process the petabytes of unanalyzed data.Quantum computers could empower machine learning by enabling AI programs to search through these gigantic datasets concerning medical research, consumer behavior and financial markets—and make sense of them.

Optimization

Imagine, say, you are a traveling salesman. You wish to visit a handful of cities and want to know what the most optimal routes would be. This would be an example of an optimization problem. It sounds simple enough, but, in reality, the process can get quite involved as you up the number of variables. With only 270 destinations, for example, there are more combinations of travel than atoms in the universe. With quantum computers, however, we could expect a machine to be able to handle almost innumerable permutations and combinations, which could advance system design and analysis in massive ways.

Biomedical Simulations

With quantum computers, we can create, simulate and model molecular structures. Researchers at Harvard University used a D-Wave One quantum computer to solve the puzzle of how some proteins fold in 2012. “The model consisted of mathematical representations of amino acids in a lattice, connected by different interaction strengths,” writes Geoffrey Brumfiel in a news article for Nature about the Harvard researchers’ protein folding models. “The D-Wave computer found the lowest configurations of amino acids and interactions, which corresponds to the most economical folding of the proteins.” While the technology was nowhere near perfect—as the researchers cited that “10,000 measurements using an 81-qubit version of the experiment gave the correct answer just 13 times”—it was able to accomplish an amazing feat by modeling the behavior of protein folding with some degree of accuracy.

Financial Services

Quantum computing is already on its way. D-wave, a company backed by Goldman Sachs and Bezos Expeditions, among others, deployed its first commercial quantum computer: the D-Wave 2000Q, a quantum annealing system with 2000 qubits and advanced feature controls. Despite their prohibitive price, these computers are being utilized by a small niche, as illustrated by Harvard’s use of D-wave’s first model back in 2012. The systems could be used for complex financial modeling and risk management within the financial industry as well. Quantum computing could be used to find “new ways to model financial data” and isolate “key global risk factors,” according to IBM. “It would be great to build systems to help Wall Street better manage risk using this type of technology,” D-Wave Systems President and CEO Vern Brownell told Bloomberg. “They spend a lot on computing power [to manage risk].”

Better Traffic Flow

Many of us are familiar with waking up early and setting off for work, only to find a traffic jam waiting on the way. And then comes the terrifying feeling that you’re going to be late for work. Google has been working on fixing this problem by monitoring traffic and suggesting alternative routes to its users. However, Volkswagen is taking it to another level with their research.In a 2017 experiment, Volkswagen tried to tackle the issue of traffic, not through monitoring but rather by optimizing traffic flow itself. They used the Quadratic Unconstraint Binary Optimization (QUBO) technique with quantum annealing computers to find the optimal route for a select number of cars and possible routes in consideration.

Better Mobile Data Coverage

We have all been in a spot where the mobile data reception is excessively bad, and we’d rather just use that slow WiFi hotspot in that nearby coffee shop. Well, it seems that a company called Booz Allen Hamilton might just have found the solution to the horrible network coverage problem, with the help of quantum computers, of course!In a 2017 publication, they suggested that optimal satellite coverage is pretty tough to figure out. This is because there are a lot of possible alignment combinations, and it is really hard to check all these combinations with classical computers.

Simulate Molecules

Molecule simulation has been a crucial field in biology and chemistry, as it helps us understand the structure of molecules and how they interact with each other. But it also helps us discover new molecules.Although classical computers nowadays may be able to simulate these molecular dynamics, there is a limitation on the complexity of molecules in a given simulation. Quantum computers are able to effectively break this barrier. So far, they’ve only been used to simulate small molecules, like beryllium hydride (BeH2), for example. It might not seem like much, but that fact that it was simulated by a seven-qubit chip shows that if we had more qubits at our disposal, we might be able to run extremely complex molecular simulations.[5] This is because the processing power of quantum computers increases exponentially as the number of qubits increase.

Break Currently Used Cryptosystems Other Than RSA

Some of us might have heard of the scare about quantum computers being able to break cryptosystems such as RSA or DSA. This seems to be true for some cryptosystems, as they rely on prime numbers to generate a key based on prime factors. An algorithm, called Shor’s algorithm, can be used by quantum computers to find the prime factors used to generate the key, and they can do it much more efficiently.But what about the other cryptosystems which do not rely on prime numbers to generate keys? There is another algorithm called Grover’s algorithm which might be used to brute force a key faster than a classical computer. However, this is not as big of a speedup as Shor’s algorithm would offer, compared to a classical computer (quadratic vs. exponential speedup). This would mean that we would need significantly faster quantum computers than the ones that currently exist to even attempt to break these cryptosystems.

More Humanlike AI

Artificial intelligence is an extremely trending field in computer science. Scientists have been trying to make AI more humanlike through the means of machine learning and neural networks. Seems terrifying, but now add quantum computers to the concoction, and it is taken to a whole new level.Neural networks run on matrix-based data sets, and the processing done in neural networks is computed through the means of matrix algebra. However, quantum computing itself fundamentally works in such a nature that matrices are often used to define and determine the quantum states of qubits.[7] So with that, any computational process done on the neural network would be similar to using transformational quantum gates on qubits. Hence, quantum computers seem like the perfect fit for neural networks incorporated in AI.

Quantum Cryptography

This is very different from post-quantum cryptography, as it is not meant to prevent quantum computers from breaking cryptosystems, though it does that, anyway. This type of cryptography uses the means of quantum mechanics itself. But how is it more versatile than other forms of cryptography?Quantum cryptography mainly focuses on the key distribution part of a cryptosystem, here two pairs of entangled qubits are used. One is sent to the receiver, while the sender keeps the other. Entangled particles in a superposition, when measured, affect the other qubit. Send a stream of these qubits, and you have a key usable for encryption.

EVOLUTION OF QUANTUM COMPUTING WITH TIME

The Commercial Future Of Quantum Computing

Can quantum computing make money?

Several major technology companies now have their own quantum computing research efforts, e.g. IBM, Microsoft (two groups!), Google.
2002: ID Quantique is first commercial company to demonstrate quantum key distribution.
2013: Mike Lazaridis (founder of BlackBerry) announces $100M venture capital fund to invest in quantum computing.
2014: The UK government announces £270M funding for research into, and commercialisation of, quantum technologies.
Estimates (perhaps not reliable) for the value of the quantum computing market are into the 10’s of billions by 2020.

The Dawn Of Quantum Computing

There is no efficient general-purpose method known to simulate quantum physics on a standard computer.

  1982: Nobel Laureate Richard Feynman asked whether quantum physics could be simulated efficiently using a quantum computer.
  “If you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy.”-by Nobel 
  Laureate Richard Feynman

  1992: David Deutsch and Richard Jozsa give the first such example.
  “The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.” - by David Deutsch 
  1993: Ethan Bernstein and Umesh Vazirani show that quantum computers can be significantly faster than classical computers, even if the classical computer is allowed a small 
  probability of error. 
  1994: Dan Simon shows that quantum computers can be exponentially faster.

These problems were all somewhat contrived...

Shor’s Algorithm

But could a quantum computer solve a problem which people actually care about?

1994: Peter Shor shows that quantum computers can factorise large integers efficiently.

     Given an integer N = p×q for prime numbers p and q, Shor’s algorithm outputs p and q.
     No efficient classical algorithm for this task is known.
     Shor’s algorithm breaks the RSA public-key cryptosystem on which Internet security is based.

Grover’s Algorithm

 One of the most basic problems in computer science: unstructured search. 
 Imagine we have n boxes, each containing a 0 or a 1. We can look inside a box at a cost of one query.(0 0 1 0 0 0 1 0)
 We want to find a box containing a 1. On a classical computer, this task could require n queries in the worst case. 
 1996: Lov Grover gives a quantum algorithm which solves this problem using about√n queries.
 The square-root speedup of Grover’s algorithm finds many applications to search and optimisation problems.

Quantum Simulation

The third important algorithmic development in the late 90’s was the resolution of Feynman’s conjecture.
1996: Seth Lloyd proposes a quantum algorithm which can simulate quantum-mechanical systems.
“A quantum computer with a few tens of quantum bits could perform in a few tens of steps simulations that would require Avogadro’s number [6×1023] of memory sites and operations 
on a classical computer.” - by Seth Lloyd 
Simulating quantum mechanics has applications to drug design, materials science, high-energy physics, ...
 

SOME EXPERIMENTAL PROGRESS

Yearwise

1997-8 Quantum teleportation demonstrated [Innsbruck, Rome, Caltech, ...]
1998 Quantum error-correction demonstrated [MIT]
2001 Shor’s algorithm factorises 15 = 3×5 using NMR [IBM]
2005 8 qubits controlled in ion trap [Innsbruck]
2008 Photonic waveguide quantum circuits demonstrated [Bristol] 
2010 Entangled states of 14 qubits created in ion trap [Innsbruck] 
2012 21 = 3×7 factorised using quantum optics [Bristol] 
2012 100µs coherence for superconducting electronic qubits [IBM]
2013 First publicly-accessible “quantum cloud” [Bristol]
2014 Superconducting qubits at fault-tolerant threshold [UCSB]

CHALLANGES FOR QUANTUM COMPUTING

Although there has been significant progress in quantum computing, the field faces a number of challenges:

The difficulty of building a large-scale quantum computer; 
The difficulty of designing new quantum algorithms; 
The difficulty of applying existing quantum algorithms to practical problems;
The difficulty of proving limitations on quantum computers. So there is still much to be done...

SUMMARY

Quantum computers can solve certain problems more efficiently than classical computers.
We don’t have large-scale, general-purpose quantum computers yet...
...but physicists and engineers are working on it!
The most important application of a large-scale quantum computer is likely to be simulating quantum-mechanical systems.
There are still many interesting open questions about the power and potential of quantum computing to be explored.