Cirq comes with a collection of example implementations of beginner, intermediate, and advanced quantum algorithms that demonstrate the main features of the library.
Implementing Shor’s Algorithm using Qiskit
Introduction
Shor’s algorithm is famous for factoring integers in polynomial time. Since the best-known classical algorithm requires superpolynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers.
The algorithm is significant because it implies that public key cryptography might be easily broken, given a sufficiently large quantum computer. RSA, for example, uses a public key N which is the product of two large prime numbers. One way to crack RSA encryption is by factoring N, but with classical algorithms, factoring becomes increasingly time-consuming as N grows large; more specifically, no classical algorithm is known that can factor in time O((log N)k) for any k. By contrast, Shor’s algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.
Like all quantum computer algorithms, Shor’s algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.
Shor’s algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.
Implementation
The algorithm can be implemented incredibly easily since Qiskit has a baked in function for the algorithm called Shor(N).
Where N will be the integer you wish to factor. For example Shor(21) will find the prime factors for 21.
You will need an API token which you can get by registering here: https://quantum-computing.ibm.com/
Implementing Grover’s Algorithm using Qiskit
Introduction
Classically, searching an unsorted database requires a linear search, which is O(N) in time. Grover’s algorithm, which takes O(N1/2) time, is the fastest possible quantum algorithm for searching an unsorted database. It provides “only” a quadratic speedup, unlike other quantum algorithms, which can provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when N is large.
Like all quantum computer algorithms, Grover’s algorithm is probabilistic, in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm.
Uses of Grover's algorithm
Although the purpose of Grover’s algorithm is usually described as “searching a database”, it may be more accurate to describe it as “inverting a function”. Roughly speaking, if we have a function y=f(x) that can be evaluated on a quantum computer, 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 a particular value of y if x matches a desired entry in a database, and another value of y for other values of x.
Grover’s algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the collision problem. In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions. This would result in a considerable speedup over classical solutions, even though it does not provide the “holy grail” of a polynomial-time solution.
Below, we present the basic form of Grover’s algorithm, which searches for a single matching entry. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand.
Implementation
You will need an API token which you can get by registering here: https://quantum-computing.ibm.com/
Fundamentals and Evolution of Quantum Computing
Quantum and its related terms are getting increasingly more eyeballs and mindshare from a wide variety of audiences – from researchers to novice enthusiasts. In this article, QuantumGuru attempts to succinctly introduce the fundamentals of quantum computing and its key principles such as superposition, entanglement, to name a few. More importantly, we have tried to touch upon and simplify the current and proposed work on quantum. Please share your feedback, your topics of interest, and how you would like us to improve.
The fundamental principles of quantum computing stem from the theory of quantum mechanics. A number of unique quantum principles highlight the clear differences between explanations provided by conventional (or classical) physics and quantum physics. Chief among these founding principles are the concepts of superposition and entanglement as well as the intrinsic randomness that appears in quantum mechanical measurements, i.e., the uncertainty principle. The application of these ideas to the theory of information has led to the development of quantum information theory. According to quantum information theory, quantum computing originates alongside quantum communication and quantum sensing, among many others.
The binary representation of data and instructions formulates conventional computing in which a register element r stores a bit b that may take on a value of either b0 or b1. Quantum computing also requires a physical register r but now the register may take the value of a quantum bit, or qubit, q. Conceptually, the qubit is defined as a normalized superposition over the exclusive outcomes b0 and b1. This hypothesis leads to a diagrammatic representation for the possible values of a qubit given as the surface of the unit sphere. Whereas the opposing north and south poles of the sphere represent the classical bit values of b0 = 0 and b1 = 1, every point on the surface corresponds to a possible qubit (q) value.
The superposition principle extends to more than a single quantum register element. Quantum mechanics permits multiple register elements to store superpositions collectively over multiple binary values. This phenomenon is known as entanglement. Quantum entanglement represents a form of information that conventional bits cannot reproduce. While the register elements remain independently addressable, the information they store is coupled and hence not expressed or represented piecewise. For example, two entangled registers may either both be in the b0 state and in the b1 state, but exclude any possibility of anti-correlated values.
The principles of superposition and entanglement lead to an important conceptual difference in the interpretation of register value. Although the qubit maps to a point on the unit sphere, observing the qubit through measurement results in a projection to either b0 or b1 values. This transition from a qubit to a bit is the infamous ‘collapse’ of the quantum state induced by measurement. The implication is that the value q itself is not observable. Instead, interpret the qubit superposition state, q in terms of the probability to observe either b0 to b1. The probabilities p0 and p1 provide the likelihood that the observed outcome will be b0 and b1, respectively.
Classical computers use electrical signals that are either on or off to convey information as bits, the smallest unit of data on a computer, represented as two binary values, zero (when ‘off’) or one (when ‘on’). Zeros and ones are strung together to form binary codes for text and other data on classical computers. Quantum computers use quantum systems, such as electrons or photons, to represent quantum bits or qubits that can be in a state of 0 or 1, or an arbitrary superposition of them, for example, an equal combination of both. Entanglement occurs when there is a non-separable joint state of multiple qubits in superposition. For example, two distant parties could share a state where both qubits are in a superposition of 0 and 1, but such that they are perfectly correlated — a superposition of both sides having 0 or both sides having 1. Balanced superpositions of this form are known as Bell pairs. Superposition and entanglement are the defining features that distinguish quantum information from classical information. In addition to enabling quantum state teleportation over quantum networks, they underpin the exponential algorithmic power of quantum computers.
Testing these intriguing principles of quantum information depends on the ability to manipulate individual atoms, molecules, electrons, and photons. Building quantum computers is challenging because nature cannot easily discern an ideal qubit. Technology-based on advanced material physics coupled with a great deal of engineering will plausibly isolate this kind of system and yet control them to perform computations with sufficient precision. Numerous different candidate systems are being explored including low-power superconducting circuits, electromagnetically trapped ions, single-atom dopants in silicon lattices, neutral atoms in optical lattices, and vacancy defects in diamond and silicon carbide as well as many, many others.
A key feature in all of these technologies is the use of sophisticated techniques to remove, reduce and control errors. Alongside state-of-the-art efforts in nanofabrication and device physics, thermodynamics control is a common approach to reduce errors. This mainly consists of refrigeration and ultra-high vacuum to isolate the device as much as possible. Shielding from stray radiations, such as magnetic fields, is also important. On top of these coarse-grained efforts, device designers also use sophisticated sequences of control pulses to negate errors. This requires a detailed understanding of device physics and it is necessary to overcome current intrinsic error rates. The methods use quantum error correction schemes to mitigate against decoherence as well as fault-tolerant protocols to extend operational sequences.
Even with the future appearance of fault-tolerant Quantum Processing Units (QPU), there is still the outstanding need to program them for practical purposes. This requires a tightly integrated system design coupled with conventional computing methods to support high-level control of quantum registers. A long history of developing quantum algorithms has provided a number of possible applications(reference to Finance use cases is shown in Figure #3) to explore. Beyond factoring, there are novel algorithms for solving linear systems of equations, simulating quantum dynamics, searching unsorted databases, and teaching machines to classify and detect patterns.
Applications of Quantum Computers
There are many foreseeable applications of quantum computers that can potentially have an impact like the Internet. We have identified following three applications that could potentially change our lives:
(I) Quantum Uncertainty can be used to create private keys for encrypting messages that are sent from one location (source) to another (destination). The hackers will be prevented from secretly copying the key because of the phenomenon of quantum uncertainty. They would have to break the laws of quantum physics to hack the key perfectly. This kind of unbreakable encryption is already being tested by banks and other institutions worldwide. With more than 17 billion connected devices globally and rising, the impact of quantum encryption on secure communications will be far reaching.
(II) Quantum technologies could also transform healthcare and medicine. Today, the design and analysis of molecules for drug development(Fig 2) is extremely challenging. Exactly describing and calculating all of the quantum properties of every atom in the molecule is a computationally difficult task even for the fastest supercomputers. However, a quantum computer could do it better as it operates using the same quantum properties as the molecule it’s trying to simulate. So future large scale quantum simulations for drug development can potentially lead to treatments for complex diseases like Alzheimer that affects millions.
(III) The most important quantum application is the teleportation(Fig 3) of information from one location to another without physically transmitting the information. Though it sounds like sci-fi, it is possible because of the fluid identities of the quantum particles. These particles can get entangled across time and space in such a way that changing something about one particle can impact the other thereby creating a channel for teleportation. It has already been demonstrated in the research labs and can be instrumental for future quantum internet. Though there is no such existing network, many companies are working on these possibilities by simulating a quantum network on a quantum computer. And a few of them have designed and implemented some interesting and new protocols. Some examples of such implementation include teleportation among different users in the network, efficient data transmission and even secure voting process.
Difference Between Quantum Computer and Classical Computer
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 can even “teleport”. It’s these strange behaviours that quantum computers aim to use to their advantage.
Classical computers manipulate ones and zeros 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”, which allows them to represent a one or a zero at the same time. Instead of analyzing 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 and consume volumes of data. An incredible 2.5 quintillion bytes of data being created every day, 90% of the world’s data has been created in the last two years alone. A staggering figure, it is expected that the volume of data is to double every two years (source). In order to adequately process h data and to extract its meaning, we require tremendously more computing power. That’s where quantum computers step in to save our day. Quantum computers can solve problems that are impossible or would take a traditional computer an impractical amount of time (a billion years) to solve. It is believed that quantum computers will change the landscape of data security. Even though quantum computers would be able to crack many of today’s encryption techniques, predictions are that they would create quantum hack-proof replacements.
Classical computers are better at some tasks than quantum computers such as email, spreadsheets and desktop publishing to name a few. The intent of quantum computers is to be a different tool to solve different problems, not to replace classical computers.
Quantum computers are great for solving optimization problems from figuring out the best way to schedule flights at an airport to determining the best delivery routes for the FedEx truck. Google announced it has a quantum computer that is 100 million times faster than any classical computer in its lab.
Every day, we produce 2.5 quintillion bytes of data (check above, my source). That number is equivalent to the content on 5 million laptops. Quantum computers will make it possible to process the amount of data we’re generating in the age of big data. In order to keep quantum computers stable, they need to be working in an extremely cold setting. That’s why the inside of D-Wave Systems quantum computer is -460 degrees fahrenheit.
According to Professor Catherine Mc Geoch at Amherst University, a quantum computer is “thousands of times” faster than a conventional computer. Superposition, as described before, is the term used to describe the quantum state where particles can exist in multiple states at the same time, and which allows quantum computers to look at many different variables at the same time. Rather than use more electricity, quantum computers will reduce power consumption anywhere from 100 up to 1000 times because quantum computers use quantum tunnelling. Quantum computers are very fragile. Any kind of vibration impacts the atoms and causes decoherence. There are several algorithms already developed for quantum computers including Grover’s for searching an unstructured database and Shor’s for factoring large numbers. Once a stable quantum computer gets developed, expect that Machine Learning will exponentially accelerate even reducing the time to solve a problem from hundreds of thousands of years to seconds.
Remember when IBM’s computer Deep Blue defeated chess champion Garry Kasparov in 1997? It was able to gain a competitive advantage because it examined 200 million possible moves each second. A quantum machine would be able to calculate 1 trillion moves per second. This year, Google stated publicly that it would produce a viable quantum computer in the next 5 years and added that they would reach “quantum supremacy” with a 53-qubit quantum computer. The top supercomputers can still manage everything a five- to 20-qubit quantum computer can, but will be surpassed by a machine with 53 qubits and will attain supremacy at that point. Shortly after that announcement, IBM said it would offer commercial quantum machines to businesses within a year.
A conventional computer simulates any information as a bit-a zero or a one. A Quantum Computer is completely different as the quantum bit has a more fluid, non-binary identity. It can exist in a superposition or a combination of zero and one, with some probability of being zero and some probability of being one. In other words, its identity is on a spectrum. For example, it could have a 70% chance of being zero and a 30% chance of being one, or 80-20 %, or 60-40 %. The possibilities are infinite and the key idea is that we have to give up on precise values of zero and one, and allow for some uncertainty. The quantum computer creates the fluid combination of zero and one. No matter what you do, the Superposition remains intact. It’s kind of like storing a mixture of two fluids, whether or not to stir the fluids remain in a mixture, but when we get to know the results the quantum computer can unmix the zero and one.
Conventional computers cannot operate the information in the aforementioned fluid combinations of zero and one. We do not experience this fluid quantum reality in our everyday lives. So, if you are confused by quantum, don’t worry you’re getting it. But even though we don’t experience quantum strangeness, we can see it’s very real effects in action. The quantum computer always won over conventional computers because it harnessed superposition and uncertainty. And these quantum properties are powerful to build future quantum technologies.
What is Quantum Computing?
Quantum computing began in the early 1980s when physicist Paul Benioff proposed a quantum mechanical model of the Turing Machine. Richard Feynman and Yuri Manin later suggested that a quantum computer had the potential to simulate things a Classical Computer could not possibly do. In 1994, Peter Shor developed a quantum algorithm for factoring integers with the potential to decrypt RSA-encrypted communications. Despite ongoing experimental progress since the late 1990s, most researchers believe that “Fault-tolerant quantum computing is still a rather distant dream.” In recent years, investment in quantum computing research has increased in the public and private sectors. On 23 October 2019, Google AI, in partnership with the U.S. National Aeronautics and Space Administration (NASA), claimed to have performed a quantum computation that was infeasible on any Classical computer.
In 2019, U.S. tech giant Google developed a 53-qubit programmable superconducting processor, named “Sycamore,” and claimed “quantum supremacy” – the point at which a quantum computer has outperformed any classical computer in the world. The 62-qubit Zu Chongzhi processor showed that China is at the same level as its U.S. counterparts in the field of superconducting quantum computing, In December 2020, Pan’s team established a quantum computer prototype named Jiuzhang, which the team said can process information 10 billion times faster than the 53-qubit quantum computer developed by Google.
Recently IBM made its aspirations more concrete by publicly announcing the roadmap for the development of its quantum computers, including the ambitious goal of building one containing 1000 qubits by 2023. In September 2020, IBM also revealed its largest quantum computer that contains 65 qubits. The plan includes building intermediate-size machines of 127 and 433 qubits in 2021 and 2022, respectively. IBM plans to follow it up with a million-qubit machine in future. IBM’s director of research, Dario Gil is confident his team can meet the schedule. “A roadmap is more than a plan and a PowerPoint presentation,” he says. “It’s execution.”
Recently IBM made its aspirations more concrete by publicly announcing the roadmap for the development of its quantum computers, including the ambitious goal of building one containing 1000 qubits by 2023. In September 2020, IBM also revealed its largest quantum computer that contains 65 qubits. The plan includes building intermediate-size machines of 127 and 433 qubits in 2021 and 2022, respectively. IBM plans to follow it up with a million-qubit machine in future. IBM’s director of research, Dario Gil is confident his team can meet the schedule. “A roadmap is more than a plan and a PowerPoint presentation,” he says. “It’s execution.”
IBM is not the only company with a roadmap to build a full-fledged quantum computer—a machine that would take advantage of the strange rules of quantum mechanics to breeze through certain computations that would not be practically possible with conventional computers. At least in terms of public relations, IBM has been playing catch-up to Google, which 1 year ago grabbed headlines when the company announced its researchers had used their 53-qubit quantum computer to solve a particular abstract problem that they claimed would overwhelm any conventional computer—reaching a milestone known as Quantum Supremacy. Google has its own plan to build a million-qubit quantum computer within 10 years. Hartmut Neven, who leads Google’s quantum computing effort, explained in an April 2021 interview, although he declined to reveal specific timelines for the advances.
In May 2021, Chinese researchers made a new breakthrough in quantum computing technology. A group of researchers from the University of Science and Technology of China (USTC) have designed and fabricated a programmable superconducting quantum computer prototype with the largest number of functional qubits in the world – 62, and achieved two-dimensional programmable quantum walks on the system.
A quantum computer is not just a more powerful version of our current computers, just like a light bulb is not a more powerful candle. You cannot build a light bulb by building better and better candles. A lightbulb is a different technology based on deeper scientific understanding. Similarly, quantum physics describes the behaviour of atoms and fundamental particles like electrons and photons. So, a quantum computer operates by controlling the behavior of these particles, but in a way that is completely different from our conventional computers. Similarly, a quantum computer is a new kind of device based on the science of quantum physics. And just like a lightbulb transform society, quantum computers have the potential to impact so many aspects of our lives, including security, our healthcare and even the internet.