Quantum Computing Overview

![image.png](https://qiita-image-store.s3.amazonaws.com/0/186167/6a81b7ea-a616-d860-0def-d99c1037deba.png)

### 1. Computers Getting Smarter than Humans
In May 2017, one of the biggest event in human history occurred. [AlphaGo](https://en.wikipedia.org/wiki/AlphaGo), an AI software developed by Google's DeepMind, beat the best Go player in the world.
Go, which is an abstract strategy board game and has more than 200 years of history, is considered the most difficult board game for AI. It was expected that it would take much more years until AI becomes able to compete with a human in Go.

In 1996, IBM's Deep Blue beat then world chess champion. The accomplishment by Alpha go was amazing. But still, more than 20 years had passed since then. What did AI take so long? 
In short, there is a tremendous difference in the number of possible combinations on board between chess and go. After the first two moves, there are 400 possible next moves in chess, on the other hand, there are close to 130,000 possibilities in go.

A Google researcher posted as below in January 2016.
- Ref: ["AlphaGo: Mastering the ancient game of Go with Machine Learning"](https://ai.googleblog.com/2016/01/) 
> But as simple as the rules are, Go is a game of profound complexity. **The search space in Go is vast -- more than a googol times larger than chess** (a number greater than there are atoms in the universe!). As a result, traditional “brute force” AI methods -- which construct a search tree over all possible sequences of moves -- don’t have a chance in Go. To date, computers have played Go only as well as amateurs. **Experts predicted it would be at least another 10 years until a computer could beat one of the world’s elite group of Go professionals. 

Finally AI has beaten human beings in board games. They are still evolving. Really fast. 
- Ref: ["AI versus AI: Self-Taught AlphaGo Zero Vanquishes Its Predecessor"](https://www.scientificamerican.com/article/ai-versus-ai-self-taught-alphago-zero-vanquishes-its-predecessor/)
Computers now can see hidden (for humans) patterns and predict what we can't. Or even in just image recognition tasks which we human beings usually do, they outperformed us according to the report more than 2 years ago. 
- Ref: ["Microsoft's Deep Learning Project Outperforms Humans In Image Recognition"](https://www.forbes.com/sites/michaelthomsen/2015/02/19/microsofts-deep-learning-project-outperforms-humans-in-image-recognition/#6226e216740b) 
 
AI is now everywhere. Knowingly or unknowingly. They gather data and improve our lives. In the near future, possibly new AI will be created by AI itself. 
- Ref: ["GOOGLE AI CREATES ITS OWN ‘CHILD’ AI THAT’S MORE ADVANCED THAN SYSTEMS BUILT BY HUMANS"](https://www.independent.co.uk/life-style/gadgets-and-tech/news/google-child-ai-bot-nasnet-automl-machine-learning-artificial-intelligence-a8093201.html)
    - Ref: ["The Military Just Created An AI That Learned How To Program Software"](https://futurism.com/military-created-ai-learned-to-program/)
("AI" is now a buzzword for marketing. Therefore, in my opinion, you don't need to take these kinds of news too much seriously and not necessary to consider that your daily life would be changed dramatically soon. But, still I'm really amazed by the speed of the innovation.)



### 2. Computer After Moore's Law
As mentioned above, in various aspects AIs are now evolving so fast. Even though still we need to consider various factors to compare human's and AI's capability, no one can hardly disagree with the speed of the computational progress.

The latest AIs can learn without human interaction and improve themselves. Then, can we just let them do their jobs and spend our time for any things we want to do? 
Unfortunately, the answer is No. There are some limitations in the current (classical) computation. To overcome the restrictions, we need to invent new computation system: [Quantum Computing](https://en.wikipedia.org/wiki/Quantum_computing). 


We are now reaching the limit of the number of transistors to be placed on a circuit. 
Moore's law was proposed in 1965 and since then it has been following the rules mostly as predicted.
- Ref: ["Moore's law - Wikipedia"](https://en.wikipedia.org/wiki/Moore%27s_law)
> Moore's law is the observation that the number of transistors in a dense integrated circuit doubles about every two years. The observation is named after Gordon Moore, the co-founder of Fairchild Semiconductor and Intel, whose 1965 paper described a doubling every year in the number of components per integrated circuit.

![image.png](https://qiita-image-store.s3.amazonaws.com/0/186167/ff7dcd40-a14e-34a0-00e5-7aa43ee5d691.png)


However, it's now getting difficult to make transistors physically smaller further more.
- Ref: ["Moore’s Law Is Dead. Now What?"](https://www.technologyreview.com/s/601441/moores-law-is-dead-now-what/)
> And a technology roadmap for Moore’s Law maintained by an industry group, including the world’s largest chip makers, is being scrapped. Intel has suggested silicon transistors can only keep shrinking for another five years.


Also, in some types of computation task, quantum computers are incomparably faster than classical computers.
For example, public key cryptosystem has been widely used for data security for decades.
Roughly speaking, its security relies on the mathematical difficulties of prime factorization for large numbers. The bigger the number gets, the longer it takes to compute factorization. As it takes to long for classical computer to solve prime factorization of large numbers, we consider that kind of cryptosystem is "practically" secure. 

[This chart](https://www.nextbigfuture.com/2017/11/how-much-faster-will-quantum-computers-be-for-more-energy-efficient-industry-and-accelerated-ai.html) shows how exponentially the duration of computation gets longer as the number of bits to factorize increases.
![image.png](https://qiita-image-store.s3.amazonaws.com/0/186167/f0454390-7e03-4c85-8b96-501a354fc110.png)

Once the number of bits to factorize reaches over 1000 bits, it takes almost a million year for the current computer to finish the computation. On the other hand, for Quantum Computers, it is just like a minutes or so. 


Even regarding Deep Learning, which allows AIs based on classical computing system to do complicated tasks such as driving vehicles as human beings, some argue that the current architecture is not enough to be able to do "any mental task that the average human can accomplish in a second or less". 
- Ref: ["Has Artificial Intelligence Hit a Wall?"](https://www.wsj.com/podcasts/has-artificial-intelligence-hit-a-wall/DEA80A1E-A0FF-4AB1-9361-1342CB50C26B.html) 
- Ref: ["Should Artificial Intelligence Copy the Human Brain?"](https://www.wsj.com/articles/should-artificial-intelligence-copy-the-human-brain-1533355265)

> Today’s deep-learning systems don’t resemble our brains. At best, they look like the outer portion of the retina, where a scant few layers of neurons do initial processing of an image. It’s very unlikely that such a network could be bent to all the tasks our brains are capable of. [...]
> Dr. Marcus says that to get to “general intelligence”—which requires the ability to reason, learn on one’s own and build mental models of the world—will take more than what today’s AI can achieve. [...]
> Until we figure out how to make our AIs more intelligent and robust, we’re going to have to hand-code into them a great deal of existing human knowledge, says Dr. Marcus. That is, a lot of the “intelligence” in artificial intelligence systems like self-driving software isn’t artificial at all. As much as companies need to train their vehicles on as many miles of real roads as possible, for now, making these systems truly capable will still require inputting a great deal of logic that reflects the decisions made by the engineers who build and test them.

(Note that this quotation is mostly just for my record. I thought this article is interesting so it's quoted in this post. However, I don't think this kind of limitation in AI algorithms will be solved by Quantum Computing. )


Anyway, because of these kind of reasons, as the next stage of computation, various companies including tech giants such as IBM, Google and Microsoft are rushing to Commercialize Quantum Computing today.
- Ref: ["Microsoft and Google prepare for big leaps in quantum computing"](https://www.ft.com/content/4b40be6c-0181-11e8-9650-9c0ad2d7c5b5)   


### 3. Flipping a "Qubit"
When the necessity of Quantum computing is mentioned on various occasions, people say this is because we simply need faster computing. Then, why can quantum computers outperform classical computers? 

In a classical computer, the basic unit of information is a bit, which can have only one of two values 0 or 1. In a quantum computer, on the other hand, the basic unit of information is known as a quantum bit or “qubit”. Qubits can be both of 0 and 1 at the same time, which is called superposition.
- Ref: ["Quantum computing - Wikipedia"](https://en.wikipedia.org/wiki/Quantum_computing#Basics)
> A quantum computer, on the other hand, maintains a sequence of qubits, which can represent a one, a zero, or any quantum superposition of those two qubit states; a pair of qubits can be in any quantum superposition of 4 states, and three qubits in any superposition of 8 states. In general, a quantum computer with n qubits can be in an arbitrary superposition of up to $2^{n}$ different states **simultaneously**. (This compares to a normal computer that can only be in one of these $2^{n}$ states at any one time).
 
Some people explain this qubit's behavior with coin flipping analogy.
Ref: ["What makes a quantum computer so different (and so much faster) than a conventional computer?"](https://www.scientificamerican.com/article/what-makes-a-quantum-comp/)

![image.png](https://qiita-image-store.s3.amazonaws.com/0/186167/e694ae26-4793-f63c-9c33-3db80ebaa2d6.png)

Once a flipped coin hit in your hand, it must be either heads[1] or tails[0]. It can't be both at the same time. This is what a classical computer is like. On the other hand, while the coin is being flipping in the air, it can be heads[1] and tails[0] at the same time (at least for most of humans. It's up to your dynamic visual acuity). Once the coin hits  the hand (once it's measured), its state has to be determined. It describes the behavior of Quantum Computer well.

This quantum behavior theoretically allows the quantum computer perform many computations simultaneously and solve a difficult subset of problems much faster than a classical computer.


### 4. Will Quantum Computer Make Current Computers Obsolete?
In my opinion, the answer to this question is also No. As described above, Quantum Computing has tremendous potential. But some researchers expect that the usage of its powers will not be so generally applicable. 

- Ref: ["The Limits of Quantum Computers (DRAFT)"](https://www.scottaaronson.com/writings/limitsqc-draft.pdf)

> This research has revealed that even a quantum computer would face significant limitations.
Contrary to the popular image, their work has revealed even a quantum computer would
face significant limitations. In particular, while a quantum computer could quickly factor
large numbers, and thereby break most of the cryptographic codes used on the Internet
today, there’s reason to think that not even a quantum computer could solve the crucial
class of NP-complete problems efficiently. [...] Limitations of quantum computers have also been found for games of strategy like chess, as well as for breaking cryptographic hash functions. 


In addition to that, probably I should've mentioned it in the first place, any quantum computer hardware has not been developed yet for practical/commercialized usage. 
This is because quantum computer hardware need very sophisticated and dedicated architecture. It depends on the implementation, but generally, the system has to keep its temperature very low as much as nearly absolute zero. As qubit contains really small energy, it easily gets affected by the temperature of external environment.
  

What if quantum computers become commercially available?
Even in that case, still I don't think quantum computers take over the place of classical computers. Rather, they are going to co-exist so that they can optimize their own computational resources.

Given the fact that quantum computers need specially designed and dedicated hardware resources, I assume it takes more than decades until we personally use quantum computers at our disposal as like Microsoft achieved with the mission statement "A computer on every desk and in every home" in the era of classical computers.

The cost of the hardware also needs to be considered. It will not get enough cheap for individuals soon. In the next decade or so, quantum computers will be used for such as business and education purpose. 

I think they will be offered as a part of Cloud Service. (Like Qubit as a Service or QaaS?). Because these 2 technology can fit together. Quantum computer hardware needs to be sophisticatedly managed/operated. It's difficult for individual companies to maintain the special facility/equipment and trained engineers. Also, as stated above, quantum computer can be used for some specific purpose. It may not be cost efficient to own quantum computers by themselves for temporary demand. 
By offering quantum computers as a service of cloud, these kind of customer's concerns can be addressed. 

I guess Microsoft is now heading to this direction. They offer [Q# Programming Language](https://docs.microsoft.com/en-us/quantum/quantum-qr-intro?view=qsharp-preview) to implements quantum algorithms.
This is how it works.
> **In this model, there are three levels of computation:**
- Classical computation that reads input data, sets up the quantum computation, triggers the quantum computation, processes the results of the computation, and presents the results to the user.
- Quantum computation that happens directly in the quantum device and implements a quantum algorithm.
- Classical computation that is required by the quantum algorithm during its execution.

Currently you can run Q# program on you machine by simulating qubits behavior. In the future, you may be able to write Q# code on your local machine and then it call quantum resource in your [Azure](https://azure.microsoft.com/en-us/) Cloud subscription when it needs qubit's computational power. 



<!--
![image.png](https://qiita-image-store.s3.amazonaws.com/0/186167/6c33030b-efde-06fe-32ad-876ba319a09d.png)

[Accenture-Innovating-Quantum-Computing-Novo.pdf]
 Information representation—In classical computing, a
computer runs on bits that have a value of either 0 or 1.
Quantum bits or “qubits” are similar in that for practical
purposes we read them as a value of 0 or 1, but they
can also hold much more complex information, or even
be negative values. Before we read their value they are
in an indeterminate state called superposition (see
graphic below) and can be influenced by other qubits
(this is called entanglement). Qubits can be realized in
a variety of ways (electron spin, light polarization, super
conducting circuits, etc.) but the results of quantum
theory hold independently of the specific mechanism of
information storage and processing.

 Information processing—In a classical computer, at
the fundamental level, bits are processed sequentially,
which is similar to the way a person would solve a
math problem by hand, one step at a time. In quantum
computation, qubits are entangled together so changing
the state of one qubit influences the state of others
regardless of their physical distance. This allows 
quantum computers to intrinsically converge on the
right answer to a problem very quickly. As a result,
qubits working together to find the optimal solution are
more efficient than certain classical approaches.


3. Use case
[Accenture-Innovating-Quantum-Computing-Novo.pdf]
 Optimization—The primary area
of focus in quantum computing
now, optimization problems
are challenges where the goal
is to find the best decision out
of a large number of possible
decisions. Optimization
problems are typically difficult
yet valuable real-world
problems to solve, and they
exist in almost every field
in which businesses operate.
Examples of optimization
problems include finding the most
cost-effective route for shipping
goods, determining the most
efficient way to extract resources
from a mine, seeking the most
productive resource allocation
involved in a production
line, looking for innovative
pharmaceutical drug discovery
methods, or identifying a
better way to manage risk in
financial portfolios. 

** Opportunities for quantum computing applications by industry
Financial Services Portfolio risk optimization and fraud detection: Quantum computing
shows promise in helping to determine attractive portfolios given thousands of
assets with interconnecting dependencies. Additionally, quantum computing
techniques could be used to more effectively identify key fraud indicators.
Healthcare Protein folding and drug discovery: Simulated annealing is an algorithm
currently used for the prediction of the effects of potential therapeutic
approaches while optimizing for non-adverse effects. Quantum computing
can replace some of these techniques, and may be able to show improvements
at scale in the next few years such as advancing drug design to the point of
providing personalized prescription drugs for individual patients.
Manufacturing Supply chain and purchasing: Supply chain optimization problems come
in many different forms, such as procurement, production and distribution. As
quantum computing improves, it will evolve from being able to solve one-time
scenarios like plan-o-grams or truck loads, to large system-wide scenarios like
store floor, regional distributions and eventually global supply chains.
Resources Asset degradation modeling and utility system distribution optimization:
Today, real-time data for operations is checked against rules, or against machine
learning models, to identify issues that might compromise availability. With
quantum computing, optimization of key systems could be an ever-present
probabilistic recommendation for cost savings. Additionally, optimal product
lifecycle and replacement could be determined at a system-wide scale to better
understand the implications, and then broken down on a part-by-part basis.
Media and Technology Advertising scheduling and ad revenue maximization systems are often
tailored on a per-customer basis. These systems collect hundreds of attributes
about a consumer’s preferences, which then need to be mapped to product
affinities and represented as a graph. Ultimately, the decision on which ad
to show a customer is an optimization of this graph, a task that a quantum
computer is well-suited to tackle.



4. Further Study
Q# 
IBM Q
https://techcrunch.com/2017/11/10/ibm-passes-major-milestone-with-20-and-50-qubit-quantum-computers-as-a-service/





[Accenture-Innovating-Quantum-Computing-Novo.pdf]
As such, it is unlikely classical computing will be replaced any time soon by quantum computing. The more likely future scenario is that quantum computing will
augment subroutines of classical algorithms that can be efficiently run on quantum computers, such as sampling, to tackle specific business problems.

Quantum computing cost per unit of performance is also still a factor, although this will change as quantum computers improve and become easier to access. 


Quantum Computing fit to Cloud


![image.png](https://qiita-image-store.s3.amazonaws.com/0/186167/9e99be5e-39a1-0fe8-c9bf-d543672323a3.png)

> The horizontal axis is the length of the number to be factored. The steep curve is NFS, with the marked point
at L = 768 requiring 3,300 CPU-years. The vertical line at L = 2048 is NIST’s 2007 recommendation for RSA
key length for data intended to remain secure until 2030. The other lines are various combinations of quantum
computer logical clock speed for a three-qubit operation known as a Toffoli gate (1Hz and 1MHz), method of
implementing the arithmetic portion of Shor’s algorithm (BCDP, D, and F), and quantum computer architecture
(NTC and AC, with the primary difference being whether or not long-distance operations are supported). The
assumed capacity of a machine in this graph is 2L2 logical qubits. This figure illustrates the difficulty of making pronouncements about the speed of quantum computers.

-->