\n", "

\n",
" ## Definition: Big O notation (Click to expand)

\n",
"For some example functions $f(x)$ and $g(x)$ and parameter $x$, the statement $f(x) = O(g(x))$ means that there exist some finite numbers $M>0$ and $x_0$ such that\n",
"$$\n",
"f(x) \\leq M g(x) \\forall x>x_0.\n",
"$$ \n",
"

\n",
"\n",
"\n",
"Big O notation is useful as it allows us to compare how the resources/runtime required by an algorithm scale with input size, independent of the specific platform and algorithm implementation under consideration. Below are examples of common scaling factors of a runtime $N$ as a function of input size $n$; it is clear that for a sufficiently large problem size the runtime of a $O(a^n)$ algorithm will exceed that of a $O(n^b)$ algorithm, where $a$ and $b$ are constants.\n",
"\n",
"\n",
"\n",
"With this notation, the property described above is expressed simply as $c(n) = O(n)$. This captures the linear behavior without needing to dwell on the specifics. Therefore, independent of whether $c(n) = n$, $c(n) = 2n$, or something else, we can simply say that $c(n) = O(n)$.\n",
"\n",
"There is a hidden assumption in what we have considered so far. By talking about the number of digits, we have assumed the use of a specific number system. However, the number of digits will depend on which number system we are using, be it decimal, binary, or something else. For example, the number of bits $n_2$ required to express a number is related to the number of decimal digits $n_{10}$ required to express the same number by\n",
"\n",
"$n_2 = \\left\\lceil \\frac{\\log 10}{ \\log 2} \\, n_{10} \\right\\rceil \\approx 3.3 \\, n_{10}.$\n",
"\n",
"Since this too is a linear relationship, it does not change how we express the complexity using big O notation. We can equally say that $c(n_2) = O(n_2)$, $c(n_{10}) = O(n_{10})$, or even $c(n_{10}) = O(n_{2})$. It is for this reason that we can often simply speak of the number of digits, $n$, without needing to specify what number system is used.\n",
"\n",
"\n",
"## 3. Complexity Theory \n",
"\n",
"Complexity theory is the study of the computational effort required to run any algorithm. By considering the best possible algorithm to solve a given problem, we can also study the computational effort inherent in solving this problem. For addition we already know the optimal algorithm, and so know that it is a problem with $O(n)$ complexity.\n",
"\n",
"Multiplication is not quite so simple. Algorithms you learned at school for multiplying two $n$-digit numbers will have required $O(n^2)$ basic operations, such as single-digit additions and multiplications. Though algorithms with lower asymptotic complexity have been found, it is widely regarded as impossible to perform multiplication with $O(n)$ complexity.\n",
"\n",
"Even so, multiplication is far from being the most complex problem. An example of a problem with far greater complexity is factorization: taking an $n$-digit number and finding its prime factors. The best known algorithm in this case has a complexity that is worse than $O\\left(e^{n^{1/3}}\\right)$. The exponential here means that the complexity grows very quickly and makes factorization a very hard problem to solve.\n",
"\n",
"To demonstrate this point using actual computation time, we can take a recent example.$^{1}$ Consider the following 829-digit number."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"rsa_250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If you try using your computer to add or multiply numbers of this size, you'll find that it can solve such problems very quickly. If you multiply the number of processors your computer has with the number of seconds it takes to get the number of core-seconds, you are sure to find that very much less than 1 core-second is required.\n",
"\n",
"However, performing factorization on this number requires a supercomputer and around 2700 core-years, which eventually yields the following two factors."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367\n",
"q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711\n",
"p*q"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For the factorization of larger numbers, we easily get to a point where a planet-sized supercomputer would need to run for the age of the universe. Clearly, any such problem is practically impossible.\n",
"\n",
"So far we have considered only mathematical operations on $n$-digit numbers, with the complexity expressed as the number of simple single-digit operations required. However, complexity theory can be used to analyze any computational method for any kind of problem, be it searching databases, rendering graphics, simulating dynamics, or traversing a dungeon in *Legend of Zelda*. In each case, we are able to find a parameter or set of parameters that serve as our input size and express the complexity in terms of this input size using big O notation. For searching a database of $N$ entries, for example, the complexity is $O(N)$.\n",
"\n",
"Formally, defining the complexity of an algorithm depends on the exact theoretical model for computation we are using. Each model has a set of basic operations, known as primitive operations, with which any algorithm can be expressed. For Boolean circuits, as we considered in the first section, the primitive operations are the logic gates. For Turing machines, a hypothetical form of computer proposed by Alan Turing, we imagine a device stepping through and manipulating information stored on a tape. The RAM model has a more complex set of primitive operations and acts as an idealized form of the computers we use every day. All these are models of digital computation, based on discretized manipulations of discrete values. Different as they may seem from each other, it turns out that it is very easy for each of them to simulate the others. This means that in most cases the computational complexity does not significantly depend on which of these models is used. Rather than stating complexity specifically for the RAM model or Turing machines, we can therefore simply speak of the complexity for digital computers."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Beyond Digital Computation \n",
"\n",
"Though digital computers are dominant now, they are not the only form of computation. Analog computers were also widely studied and used in the past. Unlike the discrete values of digital computers, these are based on precise manipulations of continuously varying parameters. It has sometimes been claimed that such devices could quickly solve problems that are intractable for digital computers. However, such claims have never been realized. A major stumbling block for analog computers is the inability to build devices with arbitrarily high precision. In digital computers, the discretization means that errors must be relatively large in order to be noticeable, and methods for detecting and correcting such errors can then be implemented. In analog computers, however, errors can be arbitrarily small and impossible to detect, but still their effects can build up to ruin a computation.\n",
"\n",
"If one were to propose an ideal model of computation, it might seek to combine the robustness of a digital computer with the subtle manipulations of an analog computer. To achieve this we can look to quantum mechanics. We have already seen that qubits are a system with discrete outputs `0` and `1`, and yet can exist in states that can only be described by continuous parameters. This is a particular instance of the well-known notion of 'wave-particle' duality that is typical of quantum systems. They cannot be fully described as either discrete or continuous, but rather a combination of the two. As Einstein said,$^{2}$\n",
"\n",
"> 'It seems as though we must use sometimes the one theory and sometimes the other, while at times we may use either. We are faced with a new kind of difficulty. We have two contradictory pictures of reality; separately neither of them fully explains the phenomena...but together they do.'\n",
"\n",
"A quantum computer, whose primitive operations are gates applied to qubits, is therefore neither analog nor digital, but something unique. In further chapters we will explore the consequences of this unique nature. We will see that quantum computers can solve problems with a radically different complexity to digital computers. In fact, quantum computing is the only known technology that can be exponentially faster than classical computers for certain tasks, potentially reducing calculation times from years to minutes. We will also explore how quantum error correction can remove the effects of any imperfections."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. When to Use a Quantum Computer \n",
"\n",
"With qubits and quantum gates, we can design novel algorithms that are fundamentally different from digital and analog classical ones. In this way, we hope to find solutions to problems that are intractable for classical computers.\n",
"\n",
"One way in which this can be done is when we have some function for which we want to determine a global property. For example, if we want to find the value of some parameter $x$ for which some function $f(x)$ is a minimum, or the period of the function if $f(x)$ is periodic. An algorithm on a digital computer might use a process in which $f(x)$ is computed for a variety of different inputs in order to get sufficient information about the global property. With a quantum computer, however, the fact that we can create superposition states means that the function can be applied to many possible inputs simultaneously. This does not mean that we can access all possible outputs since measurement of such a state simply gives us a single result. However, we can instead seek to induce a quantum interference effect, which will reveal the global property we require.\n",
"\n",
"This general description illustrates the workings of many of the quantum algorithms that have already been discovered. One prominent example is Grover's algorithm, which reduces the complexity of searching through $N$ items from $O(N)$ to $O(N^{1/2})$. This quadratic speedup could be useful in many applications with tasks that can be expressed as an unstructured search, such as optimization problems and machine learning."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"tags": [
"remove_input"
]
},
"outputs": [
{
"data": {
"text/html": [
""
],
"text/plain": [
"