Quantum Computers

 Abstract

Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas during which quantum algorithms are often applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with a stress on a broad overview of their applications instead of their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.

Introduction
A quantum computer may be a machine designed to use quantum physics to try to do things which can't be done by any machine based only on the laws of classical physics. Eventual applications of quantum computing range from breaking cryptographic systems to the planning of latest medicines. These applications are supported quantum algorithms—algorithms that run on a quantum computer and achieve a speedup, or other efficiency improvement, over any possible classical algorithm. Although large-scale general-purpose quantum computers don't yet exist, the idea of quantum algorithms has been a lively area of study for over 20 years. Here we aim to offer a broad overview of quantum algorithmics, that specialize in algorithms with clear applications and rigorous performance bounds, and including recent progress within the field.


Contrary to a rather widespread popular belief that quantum computers have few applications, the sector of quantum algorithms has developed into a neighborhood of study large enough that a quick survey like this cannot hope to be remotely comprehensive. Indeed, at the time of writing the ‘Quantum Algorithm Zoo’ website cites 262 papers on quantum algorithms. There are now a variety of fantastic surveys about quantum algorithms, and that we defer to those for details of the algorithms we cover here, and lots of more. In particular , we omit all discussion of how the quantum algorithms mentioned work. we'll also not cover the important topics of the way to actually build a quantum computer(in theory or in practice) and quantum error-correction nor quantum communication complexity or quantum Shannon theory.

Search and optimisation

One of the most basic problems in computer science is unstructured search. This problem can be formalised as follows: boxed-text

It is easy to see that, with no prior information about f, any classical algorithm, which solves the unstructured search problem with certainty must evaluate f N=2n times in the worst case. Even if we seek a randomised algorithm which succeeds, say, with probability 1/2 in the worst case, then the number of evaluations required is of order N. However, remarkably, there is a quantum algorithm due to Grover,which solves this problem using O(sqrtN) evaluations of f in the worst case (Grover’s original algorithm solved the special case where the solution is unique; the extension to multiple solutions came slightly later). The algorithm is bounded error; that is, it fails with probability ϵ, for arbitrarily small (but fixed) ϵ>0. Although f may have some kind of internal structure, Grover’s algorithm does not use this at all; we say that f is used as an oracle or black box in the algorithm.

Grover’s algorithm can immediately be applied to any problem in the complexity class NP. This class encapsulates decision problems whose solutions can be checked efficiently, in the following sense: there exists an efficient classical checking algorithm A such that, for any instance of the problem where the answer should be ‘yes’, there is a certificate that can be input to A such that A accepts the certificate. In other words, a certificate is a proof that the answer is ‘yes’, which can be checked by A. On the other hand, for any instance where the answer should be ‘no’, there should be no certificate that can make A accept it. The class NP encompasses many important problems involving optimisation and constraint satisfaction.

Given a problem in NP that has a certificate of length m, by applying Grover’s algorithm to A and searching over all possible certificates, we obtain an algorithm which uses time O(2m/2poly(m)), rather than the O(2mpoly(m)) used by classical exhaustive search over all certificates. This (nearly) quadratic speedup is less marked than the super-polynomial speedup achieved by Shor’s algorithm, but can still be rather substantial. Indeed, if the quantum computer runs at approximately the same clock speed as the classical computer, then this implies that problem instances of approximately twice the size can be solved in a comparable amount of time.

As a prototypical example of this, consider the fundamental NP-complete circuit satisfiability problem (Circuit SAT), which is illustrated below. An instance of this problem is a description of an electronic circuit comprising AND, OR and NOT gates which takes n bits as input and produces 1 bit of output. The task is to determine whether there exists an input to the circuit such that the output is 1. Algorithms for Circuit SAT can be used to solve a plethora of problems related to electronic circuits; examples include design automation, circuit equivalence and model checking. The best classical algorithms known for Circuit SAT run in the worst-case time of order 2n for n input variables, i.e., not significantly faster than exhaustive search. By applying Grover’s algorithm to the function f(x) which evaluates the circuit on input x∈{0, 1}n, we immediately obtain a runtime of O(2n/2poly(n)), where the poly(n) comes from the time taken to evaluate the circuit on a given input.

Here it is all……..go explore your interest over quantum computing and artificial intelligence accordingly!