Computing NP-complete problems in polynomial time by means of Physics

Computing NP-complete problems in polynomial time by means of Physics Trabajo de Fin de Grado Doble Grado en Ingeniería Informática y Matemáticas Autor: Víctor Carrillo Redondo Tutores: Ismael Rodríguez Laguna Javier Rodríguez Laguna Departamento de Sistemas Informáticos y Computación September 2021 i “If computer scientists had been physicists, we’d simply have declared P6=NP to be an observed law of Nature. A Nobel Prize would even be gifted for the discovery of that law. And in the unlikely event that someone later proved P=NP, a second Nobel Prize would be awarded for the law’s overthrow” Scott Aaronson [3] ii Abstract Can NP-complete problems be solved efficiently in the physical universe? Some researchers have claimed to be able to solve NP-complete problems in polynomial time by encoding the problem in the state of a physical system and letting it evolve naturally, according to the laws of physics. However, their proposals have not proven to be very effective in practice. Additionally, there are several reasons to believe that those methods would not work if P6=NP. We present some physical assumptions (both from classical physics and quantum mechanics) that would allow us to provably solve NP-complete problems in polynomial time by means of Physics, even if P6=NP and NP 6⊂ BQP. We also study if our proposals are consistent with currently known laws of Physics. Keywords: Turing machine, cellular automaton, NP-complete, classical physics, quantum mechanics, computational complexity. iii Resumen ¿Podemos resolver problemas NP-completos en tiempo polinómico dejando que ciertos entornos físicos evolucionen de manera natural conforme a las leyes de la física? Varios estudios así lo parecen afirmar, sin embargo, los métodos propuestos no han resultado ser muy efectivos en la práctica, y de hecho hay razones para pensar que no sería posible si P6=NP. Planteamos algunas suposiciones físicas (basadas tanto en la física clásica como en la mecánica cuántica) que nos permitirían resolver problemas NP-completos en tiempo polinómico en un Universo con dichas características, aunque P6=NP yNP 6⊂ BQP, y tratamos de estudiar si dichas suposiciones son consistentes con principios conocidos de la Física. Palabras clave: máquina de Turing, autómata celular, NP-completo, física clásica, mecánica cuántica, complejidad computacional. iv Agradecimientos Gracias a mi familia por haberme apoyado siempre. Gracias Adrián, Redondo, Casado, Dani, Antonio y Sergio por tantos años aguantándonos (y los que quedan). Gracias a todos los que habéis aparecido en mi vida a lo largo de estos seis años en Madrid. Gracias Esther, Alex, Carlos, Chema y Jaime, entre muchos otros. Gracias también a mis compañeros en Devo. A todos los malotes, y en particular a Gonzalo, Juan, Jorge, Fayán, Paula y Paco por vuestro apoyo y por todo lo que estoy aprendiendo de vosotros, no solo sobre desarrollo software. Y por último, gracias a Ismael por introducirme en el mundo de la complejidad computacional y por la pasión que transmite por estos temas. Gracias también a él y a Javier por su apoyo y ayuda durante el desarrollo de este trabajo. Y por todas las interesantes charlas e ideas que se nos iban ocurriendo. Espero que sigamos trabajando juntos en el futuro. v Contents Abstract ii Resumen iii Agradecimientos iv List of Figures vi Introduction 1 1 Preliminaries 3 2 Classical physics 9 2.1 Superdense information . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Hyperbolic geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Instantaneous communication . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.1 Informal explanation of the algorithm . . . . . . . . . . . . . . 10 2.3.2 Detailed explanation of the algorithm . . . . . . . . . . . . . . 13 2.3.3 Simplification of the algorithm . . . . . . . . . . . . . . . . . . 23 3 Quantum mechanics 25 3.1 Introduction to quantum mechanics . . . . . . . . . . . . . . . . . . . . 25 3.2 Variations on quantum mechanics . . . . . . . . . . . . . . . . . . . . . 33 3.2.1 Linear transformations . . . . . . . . . . . . . . . . . . . . . . . 33 3.2.2 Deterministic measurement . . . . . . . . . . . . . . . . . . . . 37 3.2.3 Probability stabilizers and enhancers . . . . . . . . . . . . . . . 43 Conclusions 48 A Linear algebra 50 Bibliography 57 vi List of Figures 1.1 RAM instructions and their semantics. . . . . . . . . . . . . . . . . . . 6 1.2 Rules of a cellular automaton. . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Rule: Send a message. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Encoding of the Boolean formula (x1∨¬x3)∧(¬x2∨x3∧x4)and of the assignment x1=x2=x3= 0,x4= 1 before and after substituting each variable with the corresponding value. . . . . . . . . . . . . . . . 11 2.3 Encoding the CNF formula (x0∨¬x2)∧(x1∨x2)as the input of our cellularautomaton.............................. 13 2.4 Rule: Moving the input formula two steps to the left and to the right. 14 2.5 Rule: Creating the first pair of assignments. . . . . . . . . . . . . . . . 15 2.6 State of our cellular automaton after generating the first pair of assignments..................................... 15 2.7 Rule: Moving down the asterisk. . . . . . . . . . . . . . . . . . . . . . 16 2.8 Rule: Sending messages to generate all possible assignments. . . . . . . 17 2.9 States of our cellular automaton during the generation all possible assignments................................... 18 2.10 State of our cellular automaton when every possible assignment has beengenerated................................ 18 2.11 Rule: Substituting the value of each literal depending on the assignment. 19 2.12 State of our cellular automaton after substituting the value of each literal. 19 2.13 Rule: Calculating the value of each clause depending on the assignment. 20 2.14 State of our cellular automaton after calculating the value of each clause depending on the assignment. . . . . . . . . . . . . . . . . . . . . . . . 20 2.15 Rule: The cell under each clause is changed with the value of the whole clause..................................... 20 2.16 State of our cellular automaton after changing the value of the cell undereachclause. ............................. 21 2.17 Rule: Calculating the value of the formula depending on the assignment. 21 2.18 State of our cellular automaton after calculating the value the formula depending on the assignment. Observe that there are four assignments that satisfy ϕ................................. 21 2.19 Rule: The value of the formula for each assignment is confirmed. . . . 22 2.20 State of our cellular automaton after confirming the value the formula depending on the assignment. . . . . . . . . . . . . . . . . . . . . . . . 22 2.21 Rule: Collecting information. . . . . . . . . . . . . . . . . . . . . . . . 22 2.22 Rule: The result of the algorithm is stored one cell down the input formula.................................... 23 2.23 State of our cellular automaton at the end of the algorithm. . . . . . . 23 3.1 State |alifor each possible value of s∈ {0,...,2n}and n= 3. . . . . 39 3.2 State Ry(π/2) |alifor each possible value of s∈ {0,...,2n}and n= 3. 39 vii Al Víctor del pasado. Lo conseguiste. 1 Introduction The concept of NP-completeness was born in 1971, when Cook [16] proved that every problem in NP is reducible in polynomial time to the Boolean Satisfiability Problem, or SAT, as we shall denote it. That means that, in a certain way, SAT is harder that any other problem in NP, because if you could solve it in polynomial time, then you could solve any other NP problem in polynomial time. That was a groundbreaking discovery, because the notion of NP-completeness seemed to characterize the class of problems for which we can efficiently verify whether a claimed solution is valid, but, however, for which there is no better algorithm than exhaustive search over a solution space that grows exponentially on the size of the instance. Moreover, in the following years a lot of important problems were proved to be NP-complete, giving evidence of their hardness. For example, the Protein Folding Problem [9,17], of great interest to the pharmaceutical industry for the discovery and development of new drugs. The consequences of proving that P=NP (and that there existed a practical algorithm for, e.g.,SAT) would be much more profound than, for example, breaking most cryptographic protocols that we currently use on the Internet (for example, to buy safely online). It would have almost metaphysical consequences. Scott Aaronson [1] said: If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps”, no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss. Even Gödel noticed it long before the P? =NP question was formulated. In a letter to von Neumann [18] in 1956, Gödel asked him about the computational complexity of deciding if a first-order formula has a proof of length at most n, a problem now known to be NP-complete [11]. He mentions what would be the implications of having a linear or quadratic time algorithm for that problem: If there were really a machine with ϕ(n)∼K·n(or even with ∼K·n2), this would have consequences of the greatest importance. It would apparently mean that in spite of the unsolvability of the Entscheidungsproblem, the reasoning of mathematicians about yes-or-no questions can be completely replaced by machines. [. . .] Now it seems to me, however, to be completely within the realm of possibility. Despite all the evidence gathered against P=NP since 1971, no one has been able to solve the problem yet. Moreover, complexity theorists have identified several reasons why solving it is so hard [6,25]. So it is natural to think of it as one of the deepest problems in mathematics. Even a one million dollar prize is awarded to anyone who can solve it [14]. Chapter 1. Preliminaries 8 every time step, however, after tsteps it can only grow a number of cells that is quadratic on t. Thus the algorithm would only require O(t3)steps. This result will allow us to work with the cellular automaton model of computation without worrying about computational complexity issues. If the number of steps needed to reach a specific configuration in a cellular automaton is polynomial on the size of the input (the initial state of the non-empty cells), then we know that we can simulate its execution in polynomial time on a Turing machine. This means that if we modelled Nature as a cellular automaton, then we would not be able to solve NPcomplete problems in polynomial time by means of Physics if P6=NP. In Section 2.3 we will study an extension of the cellular automaton model of computation based on the physical assumption that instantaneous communication is possible in our Universe. 9 Chapter 2 Classical physics In this chapter we will propose three assumptions about the physical Universe that would allow us to provably solve NP-complete problems in polynomial time using the resources of Nature, supposed that P6=NP. These are the superdense information assumption, the hyperbolic geometry assumption and the instantaneous communication assumption. The first two proposals have already been studied, so we will just mention a few results. The last proposal will be discussed in more detail. 2.1 Superdense information We describe the superdense information assumption as the ability of storing and manipulating arbitrarily big amounts of information in a finite region of space and constant time. Such assumption would allow us to solve NP-complete problems in polynomial time by means of Physics by encoding an instance of CNF-SAT in a huge integer (of exponential size) and using appropriate arithmetic operations (accessing the bit representation of the number) to evaluate a Boolean formula in parallel on all its possible assignments. Schönhage [28] showed how to do it given the ability to compute x+y, x−y,x·y,x/y and bxcin constant time. He also proved that PSPACE-complete problems can be solved in polynomial time using a similar technique. However, this assumption is not valid with our current understanding of the Universe, since it violates some well-established principles of Physics, in particular the Bekenstein bound [7]. This principle states that the Shannon entropy, i.e., the amount of information, that can be contained within a given finite region of space that has a finite amount of energy is bounded. 2.2 Hyperbolic geometry According to general relativity, the density of matter and energy in the Universe determine the curvature (and shape) of space. Depending on that, the curvature of the Universe could either be zero (the Universe is flat), positive (the Universe is locally a region of a sphere) or negative (the Universe is locally a region of a hyperboloid); and each possibility would have consequences on the geometry of space: we would have Euclidean, spherical or hyperbolic geometry, respectively. Experiments show that our Universe has zero curvature in average (up to some experimental error), so it would seem contradictory to expect it to have a non-Euclidean Chapter 2. Classical physics 10 geometry. However, would it have any consequence to computation if we dropped that assumption? The answer is yes, as shown by Margenstern and Morita [21]. They proved that NPcomplete problems can be solved in polynomial time in a cellular automaton defined on a grid of the hyperbolic plane. The idea of their proof, and the reason why it is important to do it in a hyperbolic space, is that then the number of neighbours of each cell grows fast enough as we move away from the origin that we can reach an exponential number of cells on the distance covered. 2.3 Instantaneous communication Would the ability of sending information arbitrarily fast (that is, the instantaneous communication assumption) allow us to provably solve NP-complete problems in polynomial time using the resources of the physical Universe? Based on an extension of the 2-dimensional cellular automaton model of computation where we can take advantage of the instantaneous communication assumption, we will show a polynomial time algorithm for CNF-SAT. The extension consists on a new way of changing the state of a cell in addition to the evolution rules that apply locally. Now, a cell can send a message (identifying a state of the cellular automaton) a specific number of cells away in the left or right direction. More specifically, these new rules are described as follows: Figure 2.1: If the current cell is in state σ, then the state of the cell being cpositions to the left (or to the right, respectively) will change its state to σ. More specifically, cwill be of the form c= 2k, where kis a counter that will be increased by one after each time step and that we can initialize back to 0when needed. Note that when a cell receives a message, its state during the next step of the computation will be the one received, regardless of any other rules that may apply to the destination cell. Next we will specify our algorithm for CNF-SAT. But first we want to informally describe how it works in Section 2.3.1 and then we will show the algorithm in detail in Section 2.3.2. Moreover, to make the explanation easier, we will assume that we can change the local rule of the cellular automaton during its computation (after a specific number of time steps). Later in Section 2.3.3 we will show why we can make that assumption. 2.3.1 Informal explanation of the algorithm Let ϕbe a CNF Boolean formula of nvariables and mclauses. We want to determine if ϕis satisfiable or not. The idea of our algorithm is to exploit the parallelism of cellular automata together with the ability of sending messages arbitrarily far away (in the left or right direction) to evaluate ϕon every possible assignment at the same time and then check if any of them actually make the formula true. Chapter 2. Classical physics 11 The input of our cellular automaton will be the CNF formula ϕencoded such that clauses are separated with a blank symbol, and each clause is encoded as a string of length n, where the i-th symbol indicates whether the i-th variable appears in the clause as a positive literal, as a negative literal or does not appear, having a value of 1,−1or 0, respectively. Note that the proposed encoding of a CNF Boolean formula of nvariables and mclauses is a string of (n+ 1) m−1symbols. This is a reasonable encoding, as we will prove later (see page 12), because the size of the encoded string grows at most quadratically compared to other standard encodings like the DIMACS CNF encoding [19]. The idea is to generate a string for each possible assignment of the nvariables of ϕ, encoding it so that we can easily evaluate the Boolean formula in parallel. Given an assignment of the nvariables, we will encode it as another string of length (n+ 1) m−1divided into msubstrings of length nseparated by a blank symbol. Each of those msubstrings will be identical to the others, because its i-th symbol will indicate the value assigned to the i-th variable (0or 1). Note that, then, if we see both the encoding of ϕand the encoding of a certain assignment in vertical and one string next to the other (see Figure 2.2a), we would have that, for each clause of the formula, next to the symbol encoding if the i-th variable appears as a literal in that clause there is a symbol encoding the value assigned to that variable, so we can easily substitute the value in the formula with an appropriate rule of the cellular automaton (see Figure 2.2b). Then we would just need to check if any literal in each clause is true and then if every clause is true to decide if the given assignment satisfies ϕ. (a) Encoding of the Boolean formula (left) next to the encoding of the assignment (right). (b) After substituting the value of each variable in the formula we are left with a binary string that can be evaluated as we will show later. Figure 2.2: Encoding of the Boolean formula (x1∨¬x3)∧ (¬x2∨x3∧x4)and of the assignment x1=x2=x3= 0,x4= 1 before and after substituting each variable with the corresponding value. Now the problem is how to generate such a configuration where we have the encoding of the input formula next to the encoding of a unique assignment in 2ndifferent locations of the cellular automaton grid. First we will generate the encoding of the assignments x1=··· =xn= 0 and x1= 1,x2=··· =xn= 0, and then, sending the appropriate messages, we will be keeping the invariant that at each step we have generated all the possible assignments for the first kvariables (and the rest of them Chapter 2. Classical physics 12 having value 0), so in nsteps we would have generated all 2npossible assignments to ϕ. We will specify it later. Finally, we want to evaluate the binary string that resulted from substituting the value of each variable on the encoding of the input formula (as in Figure 2.2b). Note that it represents a CNF formula whose variables have already been substituted with their actual value. To compute the value of each clause we just have to check if at least one literal is true, and this can be done following a rule that makes any cell with state 1infect any other cell in that column for n−1time steps. If there is at least one cell with state 1in a certain clause, after n−1steps all of them would be in state 1. If all of them are in state 0, they will not change their state. We then repeat the same logic to check whether every clause was true or not, but in this case we need to swap the roles of the states 0and 1, because the formula will only be true if every clause is true. Following a rule that makes any cell with state 0infect any other cell in that column for (n+ 1) m−n−1time steps. Before showing the details of the algorithm, we are going to prove the claim that we made previously (in page 11) regarding the length of the proposed encoding. That is, that its length will grow at most quadratically compared to the size of other standard encodings such as the DIMACS CNF encoding. The DIMACS CNF encoding of a CNF formula of nvariables and mclauses is the concatenation of the encoding of each clause separated by a symbol 0(and adding blank symbols when needed). And each clause is encoded as the concatenation of the number of the variables that appear on it, where negated variables appear as negative integers (also adding blank symbols when needed). Proof. Let ϕbe a CNF Boolean formula of nvariables and mclauses, where each clause has lcliterals, for c∈ {1, . . . , m}. Let fbe the function that maps the length of the DIMACS CNF encoding of ϕto the length of our encoding of ϕ, and let kbe the length of the DIMACS CNF encoding of ϕ. We have that kcan be, at most, equal to m X c=1 (2lc+ 1) log2(2n+ 2) = m X c=1 (2lc+ 1) 1 + log2(n+ 1), because we need to encode 2n+ 2 symbols as bit strings and for each clause we have 2lc+ 1 symbols (each literal is followed by a space and at the end we have to write the symbol 0), for c∈ {1, . . . , m}. And in that case, k= m X c=1 (2lc+ 1) 1 + log2(n+ 1)≥ m X c=1 lc=:l≥m, where the first inequality is due to the fact that log2(n+ 1) ≥0and the last holds because in every clause there must be at least one literal (we could remove that clause if not). Moreover, note that n≤l, because if n > l, then some variable would never appear as a literal in the formula, so we could remove it. Chapter 2. Classical physics 13 Now we can prove our claim, because we have that f(k) = f  m X c=1 (2lc+ 1) log2(2n+ 2)  =C(n+ 1) m−1 ≤C(k+ 1) k−1∈ O(k2), where C= log2|S|, that is, Cis the number of bits needed to encode every possible state of the cellular automaton (note that Cis a constant number). That is, fgrows at most quadratically in k. 2.3.2 Detailed explanation of the algorithm We will assume that we can change the local rule of the cellular automaton after a certain number of steps during its execution to explain the algorithm easier. However, we will show in Section 2.3.3 how that assumption can be eliminated. To see how our algorithm for CNF-SAT works we will be following the computation steps for a specific instance of the problem. We want to check whether the Boolean formula ϕ(x1, x2, x3) = (x1∨¬x3)∧(x2∨x3)in CNF is satisfiable or not. Since this is a very small instance (just three variables and two clauses), we can easily verify that ϕis indeed satisfiable, because, for example, the assignment x1=x2=x3= 1 makes it true. We recommend the reader to watch this video showing the full execution of the algorithm [12]. To begin, we have to represent the CNF formula ϕas a string that will be the input to our cellular automaton. Using the encoding that we proposed on the previous section we have that the input of our cellular automaton is as shown in Figure 2.3. Figure 2.3: Encoding the CNF formula (x0∨¬x2)∧(x1∨x2)as the input of our cellular automaton. The idea now is to replicate the information about ϕin 2ndifferent locations (sufficiently far away from each other) together with a unique assignment of the nvariables to evaluate all 2nof them in parallel. Note that the ability of sending information at arbitrarily long distances (in particular, distances that may grow exponentially) is necessary in order to populate an exponential number of cells in polynomial time, because the number of reachable cells grows only quadratically with the distance (unlike the case of the cellular automaton on the hyperbolic plane, as we mentioned before in page 10). Chapter 2. Classical physics 14 First, we will generate the encoding of the assignments x1=··· =xn= 0 and x1= 1,x2=··· =xn= 0. This can be easily achieved following the rules in Figure 2.4 for two steps and then the rules in Figure 2.5 for one step. Reaching the state shown in Figure 2.6. (a) Moving the input formula one step to the left and to the right, annotating it properly. (b) Moving the input formula a second step to the left and to the right. (c) Removing the intermediate result produced when the formula was moved a first step to the left and to the right. Figure 2.4: Moving the input formula two steps to the left and to the right. Chapter 2. Classical physics 15 (a) Creating the first assignment to the left of the input formula, where the first variable is assigned the value 1and the rest are assigned the value 0. (b) Creating the first assignment to the right of the input formula, where all variables are assigned the value 0. Figure 2.5: Creating the first pair of possible assignments to the input formula. The asterisk at the first symbol of each assignment will be used to track which of the 2npossible assignments have already been produced. Figure 2.6: State of our cellular automaton after generating the first pair of assignments. Note in Figure 2.6 that the first cell of each block of assignment cells (those with the subscript E) is annotated with an asterisk. That asterisk will be used to track which (and how many) assignments have already been generated. In particular, if the asterisk is in the i-th cell, it means that we have generated all 2ipossible assignments for the first ivariables (the rest of the variables would have the value 0), so when it reaches the n-th cell it would mean that we have generated all 2npossible assignments. We will keep this invariant throughout the following steps. For the next 2 (n−1) steps we will be repeating the following sequence of rules n−1times. First, we will move the asterisk one cell down following the rules from Figure 2.7 for one step. Note that, then, we have to generate new assignments to keep the invariant true, which means doubling the number of already generated assignments and making sure that we do not repeat any of them. It is easy to check that we achieve it by following the rules in Figure 2.8 for another step, where the value kis initially 1and will be increased in each iteration up to n−1. The reason is that the already Chapter 2. Classical physics 16 generated assignments are not changed, but we also copy them in another place where we change the value assigned to the new variable, so the number of assignments is doubled and they are all new. (a) Moving the asterisk one cell down. (b) Removing the asterisk from the cells already having it. Figure 2.7: The execution of these rules at the same time has the effect of moving the asterisk one cell down and removing it from the cell where it was previously. (a) Sending the encoding of ϕ2kcells to the left and to the right. Chapter 2. Classical physics 17 (b) Generating a new assignment from each one already calculated. Figure 2.8: The appropriate messages are sent to the left and to the right to send the encoding of ϕand to generate new assignments. The value of kis a variable of the cellular automaton that initially has value 1and then keeps increasing by one every time this rule is executed (up to n−1, because we are repeating this rule n−1times). Note that there are three variables (i.e.,n= 3), so we would be repeating the sequence of rules explained before just two times, going through the states shown in Figure 2.9. Chapter 2. Classical physics 24 Then, we just need to study four more cases: how to change the local rule after generating all the possible assignments (expansion phase), after repeating the rules from Figure 2.13 for n−1steps (flooding the clause phase), the rules from Figure 2.17 for (n+ 1) m−n−1steps (flooding the formula phase) and the rules from Figure 2.21 for n+ 1 steps (collecting the results phase). The general idea is to repeat those rules until a specific condition (that can be easily checked by the cellular automaton) takes place. Then we could use a similar trick as in Proposition 2.1 to annotate the cells that detect that condition and start communicating it to their neighbours. Flooding the clause phase We need to make sure that we have repeated that rule for, at least, n−1steps to make sure that if any literal was true, then every cell in that clause has already changed its state to 1. So we could annotate the first cell of each clause and applying the same rule, but also annotating the cell below an already annotated one until we notice that we cannot annotate any other cell because we have reached an empty cell. Since the length of each clause is n, we would repeat the new rule for the required time steps. Flooding the formula phase We could apply a similar idea to the previous one, but focusing in this case in the whole formula. We need to repeat the flooding rule for at least (n+ 1) m−n−1steps, but using the previous trick we would need to annotate every cell in the formula, of length (n+ 1) m−1. Collecting the results phase In this case we could end before the n+ 1 steps just checking if the cell under the input formula changes its state. Note that the input formula is the only column of cells with states from {−1,0,1}. Expansion phase In this case we are moving the asterisk one cell down each step, so we could finish this phase when we cannot move the asterisk more cells down because we already reached an empty cell. 25 Chapter 3 Quantum mechanics What if we tried to take advantage of the quantum rules of Nature to solve NPcomplete problems in polynomial time? When quantum computing came along, it was believed that the inherent parallelism of quantum mechanics would allow us to finally achieve it. Indeed, you can naively argue that you just need to prepare a superposition of all possible assignments to a Boolean formula and evaluate it in parallel to check whether it is satisfiable or not, and thus solving SAT or TAUT in polynomial time. However, as we shall see, it is not that easy: performing such computation would leave us with a state that gives us little information about the satisfiability of the formula. Moreover, it is known that NP 6⊂ BQP1relative to an oracle [8]. And while this result does not rule out the possibility of NP ⊂BQP, it tells us that we would need to exploit the structure of NP-complete problems in a nontrivial way in order to solve them in quantum polynomial time. This leaves us with the question of how should the theory of quantum mechanics change to be able to provably solve NP-complete problems in polynomial time with a quantum computer. We will address that problem later in this chapter, but before that, we shall review the basics of quantum mechanics and how it applies to quantum computation. 3.1 Introduction to quantum mechanics In order to study the behaviour of quantum systems and how to apply them to computation, we will introduce the postulates of quantum mechanics, the mathematical formalization of the quantum theory. We refer the reader to Appendix A for a review of some of the mathematical concepts and notation that we will be using. First, it is important to see how to mathematically represent a physical system and its state. Postulate 1. Each isolated physical system is associated with a complex vector space with inner product (i.e., a Hilbert space), known as the state space of the system. The state of the system is described by a unit vector in its state space, known as the state vector. Note that quantum mechanics does not tell us what is the state space of a given physical system and that modelling a physical system is a nontrivial task for physicists. However, we will not have to deal with such difficulties here. Indeed, we are concerned with one of the simplest quantum systems, the qubit. 1BQP is the class of decision problems solvable in quantum polynomial time with an error probability of at most 1/3for all instances. Chapter 3. Quantum mechanics 26 Example. The state space of a qubit is C2. Let {|0i,|1i} be an orthonormal basis for that state space, we shall refer to it as the computational basis. Then, the state vector |ψiof a qubit can be written as |ψi=α|0i+β|1i, where α, β ∈C. The condition that |ψiis a unit vector is equivalent to 1 = hψ|ψi=αα +ββ =|α|2+|β|2. The state vectors |0iand |1iare named in that way in analogy with 0and 1, the possible states of a bit, the basic unit of classical information. However, qubits can also be in a superposition of those states, i.e.,α|0i+β|1iwhere α, β ∈Csuch that |α|2+|β|2= 1.αand βare called the amplitudes of the states |0iand |1i, respectively.  Since we will be working with systems made up of multiple qubits, we need a way to represent the state space of such systems. The next postulate describes how the state space of a composite system is built up from the state spaces of the component systems. Postulate 2. The state space of a composite physical system is the tensor product of the state spaces of the component systems. In addition, the state vector of the composite system is the tensor product of the state vectors of the component systems. That is, if there are ncomponent systems and the i-th system is in the state |ψii, for i∈ {1, . . . , n}, then the composite system is in the state |ψ1i⊗···⊗|ψni. Note that it does not mean that any state vector of a composite physical system can be written as the tensor product of state vectors of the component systems. In fact, there are state vectors like |0i⊗|0i+|1i⊗|1i √2, known as entangled states, that cannot. Example (Multiple qubits).From postulate 2 we know that the state space of a system of nqubits is Nn i=1 C2=C2n. Note that the dimension of the state space grows exponentially on the number of qubits, so we can have a superposition of an exponential number of states. The computational basis for that space is given by |0i,|1i⊗n=n|ψ1i⊗···⊗|ψni:|ψii ∈ |0i,|1io. For example, for n= 2, the computational basis of C2⊗C2=C4is |0i⊗|0i,|0i⊗|1i,|1i⊗|0i,|1i⊗|1i, that we will write as |00i,|01i,|10i,|11ifor the sake of readability. In general, for nqubits we might write the vectors of the computational basis as |xi:x∈ {0,1}n in lexicographic order (as in the n= 2 example).  In order to perform computations with quantum systems, we are interested in how they may change with time. The following postulate describes such changes. Chapter 3. Quantum mechanics 27 Postulate 3. The time evolution of a closed quantum system is described by unitary transformations. That is, the state of the system at time tis related to the state of the system at time t0by a unitary operator Uas follows ψ(t)=Uψ(t0). That means that the transformations that we are allowed to perform on any quantum system, and in particular on qubits, must be given by a unitary operator. This is important because the unitarity of quantum states is preserved by unitary transformations (see definition A.12). Example. To see some examples, consider the unitary transformation Xgiven by X:|0i 7→ |1i |1i 7→ |0i, which is the quantum analogous of the classical not gate. A more interesting example is the Hadamard transformation H, given by H:|0i 7→ |0i+|1i √2=|+i |1i 7→ |0i−|1i √2=|−i. This unitary transformation has interesting properties, like being self-adjoint (so it is its own inverse), i.e.,H=H†, and that if we apply it to nqubits all with state |0i, we would get a superposition of the 2nstates in the computational basis of nqubits. That is, H⊗n|0ni=1 √2nX x∈{0,1}n|xi. More generally, it verifies that for any y∈ {0,1}nwe have that H⊗n|yi=1 √2nX x∈{0,1}n (−1)x·y|xi, where x·yis the inner product of xand yseen as vectors in {0,1}n. We will use this identity later.  Finally, we are interested in how we may access the information stored on a qubit. While getting the state of a bit has no consequences, we cannot measure the state of aqubit without changing its state, and moreover, the result of a measurement may be random! The following postulate shows how the measurement of the state of a quantum system works and what effects it has. Postulate 4. Quantum measurements are described by a collection {Mm}mof measurement operators on the state space of the system being measured. The index m refers to the possible measurement outcomes. The measurement operators must verify the completeness equation X m M† mMm=I. Chapter 3. Quantum mechanics 28 If the state of the system is |ψi, the probability of getting the outcome mwhen measuring is p(m) = hψ|M† mMm|ψi, and in that case, the state would collapse to Mm|ψi qhψ|M† mMm|ψi . The completeness equation shows that the probabilities of getting any outcome m sum up to one, because 1 = hψ|ψi=hψ|I|ψi=hψ| X m M† mMm!|ψi=X mhψ|M† mMm|ψi=X m p(m). Example (Measurement of a qubit in the computational basis).For example, we may want to perform the measurement of a qubit with state |ψi=α|0i+β|1iin the computational basis, which is described by the measurement operators M0=|0ih0| and M1=|1ih1|. We can easily check that they verify the completeness equation, for example, seeing the matrix representation of the measurement operators in the computational basis. Since M0=|0ih0|= 1 0 0 0!and M1=|1ih1|= 0 0 0 1!, we have that M† 0M0+M† 1M1=M2 0+M2 1=M0+M1=I. We could have also noticed that M0and M1are projections that verify that M† m=Mmand M2 m=Mm for m∈ {0,1}and because of proposition A.4. Measuring the state |ψi, we would obtain the outcome 0with probability p(0) = hψ|M† 0M0|ψi=hψ|M0|ψi=hψ|0ih0|ψi=αα =|α|2, and in that case the state would collapse to M0|ψi |α|=|0ih0|ψi |α|=α |α||0i. On the other hand, we would obtain the outcome 1with probability p(1) = hψ|M† 1M1|ψi=hψ|M1|ψi=hψ|1ih1|ψi=ββ =|β|2, and the state would collapse to M1|ψi |β|=|1ih1|ψi |β|=β |β||1i. Note that |α|2+|β|2= 1. Another important observation from the previous example is that after the measurement the state collapses to one of the states of the computational basis, but multiplied by a certain unitary complex number. In general we can ignore that factor. To see Chapter 3. Quantum mechanics 29 it, let |ψiand |φibe two states such that |ψi=eiθ|φifor some θ∈[0,2π)and let {Mm}mbe a collection of measurement operators. Then, when measuring the state |ψi, the probability of obtaining the outcome mis hψ|M† mMm|ψi=eiθhφ|M† mMmeiθ|φi =e−iθeiθhφ|M† mMm|φi =hφ|M† mMm|φi, which equals the probability of obtaining the outcome mwhen measuring the state |φi. In most cases we will be concerned with a special class of measurements, known as projective measurements. Indeed, it can be shown that they are equivalent to general measurement operators. A projective measurement is described by a collection {Pm}mof measurement operators that, in addition to satisfying the completeness equation, also satisfy the conditions that Pmare orthogonal projectors. That is, the Pmare self-adjoint and PmPm0=δm,m0Pm. Let us note that in that case the completeness equation can be rewritten as I= n X i=1 P† mPm= n X i=1 P2 m= n X i=1 Pm. So, if |ψiis the state of the system, the probability of getting outcome mwhen measuring is p(m) = hψ|Pm|ψi, and in that case, the state would collapse to Pm|ψi phψ|Pm|ψi. This allows us to define what measuring in a basis is. Let |ψii:1≤i≤nbe an orthonormal basis of our state space. Then, a measurement with respect to that basis is the projective measurement with projectors Pi=|ψiihψi|:1≤i≤n. Example. For example, let us suppose that we have the following two-qubit state |ψi=α|00i+β|01i+γ|10i+δ|11i that we want to measure in the computational basis. Then, we would get the outcome, e.g.,01, with probability p(01) = hψ|P01 |ψi=hψ|01ih01|ψi=ββ =|β|2. And in that case, the state would collapse to |01i, modulo a unitary complex number.  Example. Another example of a measurement that we could perform is measuring just one qubit of a multiple qubit system. Following the previous example, let |ψi=α|00i+β|01i+γ|10i+δ|11i Chapter 3. Quantum mechanics 30 be the state of our two qubit system. And suppose that we only want to measure the second qubit in the computational basis. That measurement is described by projectors I⊗|0ih0|, I ⊗|1ih1|. Thus, we would obtain the outcome 0with probability p(0) = hψ|I⊗|0ih0||ψi =hψ|I⊗|0ih0|α|0i+γ|1i⊗|0i+β|0i+δ|1i⊗|1i =hψ|α|0i+γ|1i⊗h0|0i|0i+β|0i+δ|1i⊗h0|1i|0i =hψ|α|00i+γ|10i =αα +γγ =|α|2+|γ|2, leaving the state as I⊗|0ih0||ψi q|α|2+|γ|2=α|00i+γ|10i q|α|2+|γ|2. Or we could obtain the outcome 1with probability p(1) = hψ|I⊗|1ih1||ψi =hψ|I⊗|1ih1|α|0i+γ|1i⊗|0i+β|0i+δ|1i⊗|1i =hψ|α|0i+γ|1i⊗h1|0i|1i+β|0i+δ|1i⊗h1|1i|1i =hψ|β|01i+δ|11i =ββ +δδ =|β|2+|δ|2, and collapsing the state to I⊗|1ih1||ψi q|β|2+|δ|2=β|01i+δ|11i q|β|2+|δ|2. This example can be intuitively seen if we rewrite the state |ψias |ψi=α|0i+γ|1i⊗|0i+β|0i+δ|1i⊗|1i.  Up to this moment we have reviewed the mathematical formulation of quantum mechanics, but we are now interested in its applications. In particular, we will discuss two important consequences of the quantum theory: the no-cloning theorem and the impossibility of distinguishing arbitrary quantum states (and how they relate to each other). The no-cloning theorem states that, unlike with classical information, we cannot create a perfect copy of a quantum system. This is shown by the following result. Theorem (No-cloning theorem).Let Hbe the state space of a given quantum system and let |γi ∈ H be a unit vector. Then, there does not exist any linear operator Uon H⊗H such that U|ψi⊗|γi=|ψi⊗|ψifor any |ψi ∈ H. That is, we cannot create a copy of an arbitrary quantum state. Chapter 3. Quantum mechanics 31 Proof. By contradiction, let us assume that such unitary operator Uexists, and let |ψi,|φi∈Hbe two states we want to clone. So we have that U|ψi⊗|γi=|ψi⊗|ψiand U|φi⊗|γi=|φi⊗|φi. Taking the inner product we have that hψ|⊗hγ|U†U|φi⊗|γi=hψ|⊗hγ||φi⊗|γi=hψ|φihγ|γi=hψ|φi and, on the other hand, hψ|⊗hψ||φi⊗|φi=hψ|φihψ|φi=hψ|φi2. Since both values must be equal, we have that hψ|φi=hψ|φi2, which leaves us with two possibilities: either hψ|φi= 0 or hψ|φi= 1. That is, either |ψiand |φiare the same state or they are orthogonal. Anyway, we cannot clone arbitrary quantum states, which contradicts the hypothesis.  We can start feeling that the restriction that quantum transformations must be given by unitary operators is limiting us. We will see this again later. Although the previous result prevents us from cloning arbitrary quantum states, it is still possible to do it in some cases. The following example shows one of them. Example. Let |ψi,|φi ∈ C2be two orthogonal qubits. Without loss of generality we may assume them to be the states |0iand |1i(if not, we just change the states to the computational basis). And let |γibe an unknown state that is equal to one of them. Let CNOT be the two qubit unitary transformation given by CNOT : |00i 7→ |00i |01i 7→ |01i |10i 7→ |11i |11i 7→ |10i. Where the first qubit is the control qubit whose value determines if the second qubit is negated or not. We can see that CNOT is unitary because it transforms an orthonormal basis into another orthonormal basis (see proposition A.13). Moreover, notice that it allows us to clone the state |γigiven that it is either |0ior |1i. Another problem that classically is trivial but cannot be solved with certainty for quantum systems is the problem of distinguishing quantum states. Let |ψii:1≤i≤n be a set of quantum states and let |γibe an unknown state that belongs to that set. We have to identify which state it is. This problem is related to the problem of cloning quantum states. Actually, if we could distinguish a pair of arbitrary quantum states, then we would be able to clone them. Example. Let |ψiand |φitwo qubits, not necessarily orthogonal, let B1=|ψi,|ψ0i and B2=|φi,|φ0itwo orthonormal basis in C2and let |γibe an unknown state equal to one of |ψiand |φi. We are going to show that if we can identify which state it is, then we could clone it. Chapter 3. Quantum mechanics 32 Let U1=|ψih0|+|ψ0ih1|and U2=|φih0|+|φ0ih1|be the unitary operators that change from the computational basis to B1and B2, respectively. If we can distinguish if |γiis equal to |ψior |φi, we just have to apply to a qubit with state |0ithe transformation U1or U2, respectively.  But it turns out that we can distinguish a quantum state from an orthonormal set. Example. Let |ψii:1≤i≤nbe an orthonormal set of states and let |γibe an unknown state from that set. Consider the set of projections Pi=|ψii|ψii:1≤i≤n, that together with P0=I−Pn i=1 Pidefine a projective measurement. Then, if |γiis |ψi0ifor a certain i0∈ {1, . . . , n}and we measure that state with the measurement defined by projections {Pi:0≤i≤n}, we would get the outcome i0with probability p(i0) = hγ|Pi0|γi=hψi0|ψi0ihψi0|ψi0i= 1. And thus, reliably distinguishing the state.  Finally, we will prove that it is not possible to distinguish a state from a set of non-orthogonal states. Proof. Let |ψ1iand |ψ2ibe two non-orthogonal quantum states that we want to distinguish. The idea is to perform a measurement of our unknown state |γidescribed by measurement operators {Mm}m. Depending on the outcome m, we will try to guess what the value of the index i∈ {1,2}was according to a predefined rule fsuch that f(m) = i. Let E1=X m:f(m)=1 M† mMmand E2=X m:f(m)=2 M† mMm, that verify that E1+E2=Ibecause of the completeness equation. Also note that E1and E2are positive-semidefinite operators (see proposition A.17). If we could distinguish the states |ψ1iand |ψ2iwith the measurement described above, we would have that the probability of measuring and obtaining an outcome m such that f(m)matches the desired index is 1. And that condition can be expressed as follows hψ1|E1|ψ1i= 1 and hψ2|E2|ψ2i= 1. Since hψ1|E1|ψ1i= 1 = hψ1|ψ1i=hψ1|(E1+E2)|ψi, we must have that hψ1|E2|ψ1i= 0. Moreover, since E2is a positive-semidefinite operator, there exists an operator Ssuch that S†S=E2, so 0 = hψ1|E2|ψ1i= hψ1|S†S|ψ1i, which is equivalent to S|ψ1i= 0. This will lead to a contradiction, because if we pick an orthonormal basis {|ψ1i,|φi} of the vector space spanned by vectors |ψ1iand |ψ2i, we can write |ψ2i=α|ψ1i+β|φi for some α, β ∈Csuch that 0<|α|,|β|<1. Applying Sto |ψ2iwe get that S|ψ2i=αS |ψ1i+βS |φi=βS |φi, so 1 = hψ2|E2|ψ2i=hψ2|S†S|ψ2i=|β|2hφ|S†S|φi<hφ|E2|φi ≤ 1. Chapter 3. Quantum mechanics 33 Where the last inequality comes from the fact that hφ|E2|φi ≤ hφ|E1|φi+hφ|E2|φi=hφ|(E1+E2)|φi=hφ|φi= 1 because both E1and E2are positive-semidefinite operators.  That means that it would be against all known laws of Physics if we could reliably clone arbitrary quantum states or distinguish non-orthogonal quantum states. 3.2 Variations on quantum mechanics Now we will explore some variations on quantum mechanics that would allow us to provably solve NP-complete problems in quantum polynomial time. In particular, we want to study what would happen if we could perform transformations other than unitary to qubits and if the measurement of quantum systems was a bit different. 3.2.1 Linear transformations Many arguments against quantum computers claim that we do not really know whether the theory of quantum mechanics will remain valid in the regime tested by quantum computers. However, most of the proposals for how quantum mechanics could be wrong suggest a world with more computational power than BQP (see [2, p. 7]). For example, what would happen if we added a tiny nonlinear term to the Schrödinger equation? Abrams and Lloyd [4] proved that they could solve NP-complete (and even #P-complete) problems in quantum polynomial time if they could use some nonlinear transformations that were naturally defined based on a nonlinear model of quantum mechanics described by Weinberg [29]. Moreover, if we could use arbitrary nonlinear operators then we could solve PSPACE-complete problems in polynomial time [2, p. 8]. That begs the question whether we could relax that hypothesis and define a model of quantum mechanics where we could perform certain types of linear transformations to quantum states that would allow us to provably solve NP-complete problems in quantum polynomial time, and what physical consequences it would have. In particular, we focused on the following types of linear transformations: 1. Unitary operators. This leads to the model of quantum mechanics that we have already introduced. As we mentioned before, at the time of writing this it is unclear whether NP ⊂BQP, but there is no evidence that it is the case and that we would be able to solve NP-complete problems with standard quantum computers in polynomial time. 2. Linear operators with unitary complex eigenvalues. 3. Linear operators whose determinant is a unitary complex number. 4. Invertible linear operators. Note that each type is contained in the following ones in the list (see, for example, proposition A.14), so we are interested in identifying what is the slightest modification of quantum mechanics that would let us solve NP-complete problems in polynomial time (if any among those above applies). It is also important to notice that we could have focused on another classification of linear transformations that may (or not) have led to a better understanding of the problem, but we consider that this approach will shed light on that question. Chapter 3. Quantum mechanics 40 Rotations around the y-axis are given by the unitary transformation Ry(θ)such that Ry(θ):|0i 7→ cos θ/2|0i+ sin θ/2|1i |1i 7→ −sin θ/2|0i+ cos θ/2|1i. In our particular case, where θ=π/2, we would have the transformation given by Ry(π/2) :|0i 7→ cos π/4|0i+ sin π/4|1i=1 √2|0i+|1i |1i 7→ −sin π/4|0i+ cos π/4|1i=−1 √2|0i−|1i. Note that Ryπ/2=XH. So applying that rotation to our state we would have that Ryπ/2   (2n−s)|0i+s|1i q(2n−s)2+s2  =(2n−s)Ryπ/2|0i+s Ryπ/2|1i q(2n−s)2+s2 =(2n−s)|0i+|1i+s−|0i+|1i √2q(2n−s)2+s2 =(2n−2s)|0i √2q(2n−s)2+s2 +2n|1i √2q(2n−s)2+s2 =|φi. If we measured that state in the computational basis, since hφ|0ih0|φi=(2n−2s)2 2(2n−s)2+s2 and hφ|1ih1|φi=22n 2(2n−s)2+s2, we would have that hφ|0ih0|φi<hφ|1ih1|φi if and only if |2n−2s|<|2n|, which will be true for every s∈ {1,...,2n−1}, and we would get the outcome 1. On the other hand, for s∈ {0,2n}we would have that hφ|0ih0|φi=hφ|1ih1|φi, getting any outcome with probability 1/2. But note that we can discard the case s= 2nsimply by evaluating our Boolean function ϕon any assignment. If that assignment makes ϕtrue, then we have already decided if it is satisfiable or not. On the other hand, if it does not, then we know that s < 2n. Now we can specify an algorithm to decide if ϕis satisfiable in polynomial time. First, we evaluate ϕ(0n)to decide whether it is satisfiable or s < 2n. If 0ndoes not make ϕtrue, we continue with the algorithm by preparing the state |alifrom AL Chapter 3. Quantum mechanics 41 and measure it. If the outcome of the measurement is 0, then we know that ϕis not satisfiable. On the other hand, if it is 1, it could be the case that ϕis unsatisfiable but we obtained the wrong outcome with probability 1/2. We would just need to repeat the algorithm once more. If we obtained outcome 1once again, it could be possible that ϕis unsatisfiable, but only with a probability of 1/4<1/3. That is, the overall probability of getting the right result is 3/4>2/3. That proves the following result. Theorem. If quantum measurement was deterministic in the way we proposed, then we could solve SAT with a probability of success of 2/3in quantum polynomial time. This variation of quantum mechanics would also lead to some consequences that contradict well-established physical principles. In particular, this kind of measurement would also allow us to distinguish two arbitrary qubits. To see it, imagine the two qubits that we want to distinguish as points on the Bloch sphere. If we manage to rotate them across it so that one is above the equator and the other is under it, a measurement in the computational basis would allow us to distinguish them: the outcome of measuring the state above the equator would be 0, while the outcome of measuring the other state would be 1. So the idea of the proof involves determining what is their middle point on the sphere and rotate it so that it now lays on the equator. Then, since the angles between states are preserved by unitary transformations, one of the states would be in the northern hemisphere and the other would be in the southern hemisphere (unless they were initially in the same parallel, but that case can be solved by changing the basis appropriately). Formally, we will first show how to reliably distinguish any qubit with state |ψi from the one with state |0iand then extend it to any pair of qubits. Let |γibe an unknown state that is equal to |0ior to |ψi. We are going to show how to transform that state so that measuring it would yield the result 0if it is the state |0iand it would yield the outcome 1if it is the state |ψi. Using the Bloch sphere representation, we could write |ψi= cos θ/2|0i+eiφsin θ/2|1ifor certain θ∈[0, π]and φ∈[0,2π). Since we know the state |ψithat we are trying to distinguish from |0i, we are going to suppose that we also know the values of θand φ. If θ > π/2, we could just measure the state in the computational basis to distinguish if it is |0ior not. If |γiis equal to |ψi, we would have that hψ|1ih1|ψi= sin2θ/2>1 2>cos2θ/2=hψ|0ih0|ψi, where the inequalities hold for θ∈π/2, π, so we would measure the outcome 1. Intuitively, this works because for θ > π/2the state |ψiwould already be in the southern hemisphere. On the other hand, if θ∈0, π/2, we would perform a rotation around the z-axis of −φradians followed by another rotation of (π−θ)/2radians around the y-axis before measuring the state in the computational basis. Rotations around the z-axis are given by the unitary transformation Rz(θ)such that Rz(θ):|0i 7→ e−iθ/2|0i |1i 7→ eiθ/2|1i. Chapter 3. Quantum mechanics 42 So in our case we would have the transformations given by Rz(−φ):|0i 7→ eiφ/2|0i |1i 7→ e−iφ/2|1i and Ryπ−θ 2:|0i 7→ cos π−θ 4|0i+ sin π−θ 4|1i |1i 7→ −sin π−θ 4|0i+ cos π−θ 4|1i. Those rotations would act on the state |0iin the following way Ryπ−θ 2Rz(−φ)|0i=eiφ/2Ryπ−θ 2|0i ≡Ryπ−θ 2|0i = cos π−θ 4|0i+ sin π−θ 4|1i =|ψ0i. Then, the outcome of measuring that state in the computational basis would be 0, because hψ0|0ih0|ψ0i= cos2π−θ 4>1 2>sin2π−θ 4=hψ0|1ih1|ψ0i, where the inequalities cos2(x)>1/2>sin2(x)hold for x∈0, π/4, and since θ∈0, π/2, we then have that (π−θ)/4∈π/8, π/4⊂0, π/4. The effect of those rotations on the state |ψiwould be Ryπ−θ 2Rz(−φ)|ψi=eiφ/2Ryπ−θ 2cos θ/2|0i+ sin θ/2|1i ≡Ryπ−θ 2cos θ/2|0i+ sin θ/2|1i = cos θ/2 cos π−θ 4|0i+ sin π−θ 4|1i! + sin θ/2 −sin π−θ 4|0i+ cos π−θ 4|1i! = cos π+θ 4|0i+ sin π+θ 4|1i =|ψ1i, where we used the identities sin (t+s) = sin (t) cos (s)+sin (s) cos (t)and cos (t+s) = cos (t) cos (s)−sin (s) sin (t). And in this case, the outcome of measuring |ψ1iin the computational basis would be 1, because hψ1|1ih1|ψ1i= sin2π+θ 4>1 2, Chapter 3. Quantum mechanics 43 because sin2(x)>1/2holds for x∈π/4,3π/4and (π+θ)/4∈π/4,3π/8⊂ π/4,3π/4. And thus, we can reliably distinguish both states. To extend the result for arbitrary qubits |ψiand |φi, we would just need to consider a unitary transformation Usuch that U|ψi=|0i, and then distinguish the states |0i and U|φi. In brief, although deterministically measuring quantum states would let us decide if a Boolean formula is satisfiable in polynomial time, it would also let us reliably distinguish any two qubits, and that would be contradictory the laws of Physics. 3.2.3 Probability stabilizers and enhancers In an attempt to generalize all the previous results, we noticed that we were always juggling around with how the probabilities of the different outcomes should change in order to achieve the desired behaviour for our algorithms. In particular, how we needed big amplitudes to diminish so that states with smaller amplitudes could increase their probability of being measured. Applying this to the state |ali, we wanted to increase the amplitude of the state |1icompared to the one of |0iso that we could measure the outcome 1with a probability big enough so that we could distinguish between the s= 0 and s > 0cases. This led to the concept of probability-stabilizers that we will be covering in this section. Definition 3.1. Let |ψibe a quantum state and consider the quantum measurement described by measurement operators {Mm}m. A probability-stabilizer of degree α≥1 is any transformation on the state |ψisuch that if {pm}mis the set of probabilities of obtaining any outcome mwhen measuring |ψi, then those will be changed in the following way pm7→ p0 m:=p1/α m Plp1/α l , so that X m p0 m=X m p1/α m Plp1/α l =1 Plp1/α lX m p1/α m= 1. Note that the case where α= 1 corresponds to the identity transformation. And that making α→ ∞ causes the probabilities that are greater than 0to be all equal, because for any m1and m2such that pm1, pm2>0, we have that p0 m1 p0 m2 =p1/α m1 p1/α m2 =pm1 pm21/α −−−→ α→∞ 1. The following proposition shows why this definition may be useful. Proposition 3.2. Applying a probability-stabilizer of sufficiently high degree αto the state |ali(see AL) and measuring in the computational basis would let us distinguish the cases where s= 0 and s > 0, and thus deciding if a Boolean formula ϕis satisfiable. Moreover, α∈Ω (n)is enough. Chapter 3. Quantum mechanics 44 Proof. Starting with state |ali=(2n−s)|0i+s|1i q(2n−s)2+s2 we have that the probabilities of getting each outcome are given by p0=hal|0ih0|ali=(2n−s)2 (2n−s)2+s2 for the probability of getting the outcome 0, and p1=hal|1ih1|ali=s2 (2n−s)2+s2 for the probability of getting the outcome 1. If s= 0 we have that p0= 1 and p1= 0, so those probabilities will not be affected by any probability-stabilizer. It also happens if s= 2n, because in that case p0= 0 and p1= 1. However, a probability-stabilizer would affect the probabilities if 0<s<2n, because then 0< p0, p1<1. In that case, we would have that p0 1 p0 0−−−→ α→∞ 1 understanding that quotient as a function of α. Which means that there exists a value of α≥1such that a probability-stabilizer of degree αwould have the property that, for example, p0 1 p0 0≥2 3, which would imply that p0 1≥2/5, for 0<s<2n, since p0 0+p0 1= 1. Now we could distinguish the cases s= 0 and s > 0as follows. We would apply the probability-stabilizer to state |aliand measure it a number cof times (to be chosen later). If any of the coutcomes is 1, we certainly know that s > 0. On the other hand, if all outcomes were 0we would say that s= 0. However, it might be the case where s > 0and all outcomes were 0with probability at most 3/5c. We want that value to be lower than 1/3, so we would need that 3 5c <1 3⇐⇒ clog23 5<log21 3 ⇐⇒ c > log21/3 log23/5≈2.15. So taking c= 3 we would be able to distinguish between the two cases with a probability of success of at least 2/3. To see the last part of the statement, we simply notice that p0 1 p0 0 = s2 (2n−s)2!1/α ≥ 1 (2n−1)2!1/α =1 (2n−1)2/α , Chapter 3. Quantum mechanics 45 where the inequality is tight (the equality holds for s= 1). So if we want that value to be greater that 2/3, we have that 1 (2n−1)2/α ≥2 3⇐⇒ 2 αlog2(2n−1) ≥log23/2 ⇐⇒ α≥2 log2(2n−1) log23/2. With 2 log2(2n−1) log23/2∈Θ (n) because 2 log23/2n≥2 log2(2n−1) log23/2≥2 log23/2(n−1) . So α∈Ω (n)is enough to achieve p0 1= 2/5with a probability-stabilizer of degree α. We suspect that if α∈o(n), that is, if α/n −−−→ α→∞ 0, then a probability-enhancer of degree αwould not let us distinguish the cases s= 0 and s > 0repeating the experiment at most a polynomial number of times. We could not prove it, though. This result leaves us with the question of how could we build a probability-stabilizer in polynomial time to be able to solve NP-complete problems efficiently. This does not seem to be easy because the definition of a probability-stabilizer sounds very restrictive. Could we relax the definition and still being able to prove a result like proposition 3.2? The answer is that we can. Definition 3.3. Let |ψibe a quantum state and consider the quantum measurement described by measurement operators {Mm}m. A k-probability-enhancer of degree α≥ 1is any transformation on the state |ψisuch that if {pm}mis the set of probabilities of getting any outcome mwhen measuring |ψi, then those will be changed to {p0 m}m such that p0 k≥p1/α k Plp1/α l . Note that in this definition we only require one of the possible outcomes to increase its probability at the expense of the probabilities of the other possible outcomes. The relationship between probability-stabilizers and k-probability-enhancers is that a probability-stabilizer of degree αis a k-probability-enhancer of degree αfor any possible outcome k. The reciprocal is also true: any transformation that is a kprobability-enhancer of degree αfor any possible outcome kis also a probabilitystabilizer of degree α. Proposition 3.4. Applying a 1-probability-enhancer of sufficiently high degree αto the state |aliand measuring it in the computational basis would let us distinguish the cases where s= 0 and s > 0, and thus deciding if a Boolean formula ϕis satisfiable. Chapter 3. Quantum mechanics 46 Proof. The proof is analogous to the one of proposition 3.2, because for 0<s<2n we have that p0 1 p0 0≥p1/α 1 p1/α 0 =p1 p01/α −−−→ α→∞ 1 as before, so we can guarantee that there exists a value of α≥1such that a 1probability-enhancer of degree αwould have the property that p0 1 p0 0≥2 3. The rest of the proof would be the same.  Finally, we would like to study if the proposed variations of quantum mechanics would allow us to build a 1-probability-enhancer for the state |alimeasuring it in the computational basis. The probabilities of getting outcomes 0and 1when measuring the state |aliare, respectively, p0=(2n−s)2 (2n−s)2+s2and p1=s2 (2n−s)2+s2. Example (Building a 1-probability enhancer with deterministic measurements).Applying the algorithm we described for the deterministic measurements, we would have that the probabilities would change in the following way p0 0=       1if s= 0 0if 0<s<2n 1/2if s= 2n and p0 1=       0if s= 0 1if 0<s<2n 1/2if s= 2n. And we can see that the given transformation is indeed a 1-probability-enhancer, because for s= 0 we have that p0 1=0= p1/α 1 p1/α 0+p1/α 1 for all α≥1. And for 0<s<2nwe have that p0 1= 1 ≥p1/α 1 p1/α 0+p1/α 1 . for all α≥1. However, for s= 2n, p0 1=1 26≥ 1 = p1/α 1 p1/α 0+p1/α 1 for all α≥1. But we already saw that we could discard that case: we could evaluate our Boolean formula in any assignment, and we would have that s < 2nor that the formula was satisfiable (so we would not need any 1-probability-enhancer!).  Chapter 3. Quantum mechanics 47 Example (Building a 1-probability enhancer with invertible linear operators).If the time evolution of quantum systems was described by arbitrary invertible linear operators, we would also be able to build a 1-probability-enhancer. Consider the invertible linear operator Lgiven by L|0i=|0iand L|1i= 2 |1i. Then, as we already saw, applying that transformation ntimes to the state |aliwould yield the state |φi=(2n−s)|0i+ 2ns|1i q(2n−s)2+ 22ns2 . And then, we would have that p0 1=hφ|1ih1|φi=22ns2 (2n−s)2+ 22ns2. So we have to check if 22ns2 (2n−s)2+ 22ns2=p0 1≥p1/α 1 p1/α 0+p1/α 1 =s2/α (2n−s)2/α +s2/α . for some value of α≥1. The inequality holds for s= 0 and for s= 2nfor any α≥1. For 0<s<2n, we have that 22ns2 (2n−s)2+ 22ns2≥s2/α (2n−s)2/α +s2α ⇐⇒ 22ns2(2n−s)2/α +s2/α≥s2/α (2n−s)2+ 22ns2 ⇐⇒ 22ns2(2n−s)2/α ≥s2/α (2n−s)2 ⇐⇒ 22n≥2n−s s2−2/α . Since 2n−s s≤2n−1, and the inequality is tight (the equality is reached for s= 1), we are looking for which values of α≥1we have that 22n≥(2n−1)2−2/α ≥2n−s s2−2/α . But it turns out that the inequality holds for any α≥1, because 22n= (2n)2>(2n−1)2>(2n−1)2−2/α , where we used that 0≤2−2/α < 2for α≥1in the last inequality.  48 Conclusions Can NP-complete problems be solved efficiently in the physical Universe? Our objective was to identify if any physical assumption would let us provably solve NP-complete problems in polynomial time by the means of Nature, even if P6=NP and NP 6⊂ BQP, and trying to relax them to study what would be the physical consequences if those assumptions were true. We identified five assumptions that allowed us to solve NP-complete problems in polynomial time using the resources of the physical Universe: three of them from classical physics and two from quantum mechanics. However, two of those proposals (the superdense information assumption [28] and the hyperbolic geometry assumption [21], both from classical physics) had already been studied. But, as far as we know, the other approaches have not been investigated before: the instantaneous communication assumption, the deterministic measurement (of quantum mechanics) assumption, and the non-unitary transformations assumption (this last approach had already been followed using non-linear operators [4], but based on that work we focused on studying the consequences of using a certain classification of invertible linear operators). We can draw two main conclusions from our research: 1. In order to be able to solve NP-complete problems in polynomial time, even if P6=NP, by the means of Physics we apparently need to be able to handle an exponential amount of information in polynomial time. This can be clearly seen from the superdense information assumption. But also from the hyperbolic geometry assumption and the instantaneous communication assumption: note that what those two assumptions allowed us to do is to be able to populate an exponential number of cells of a cellular automaton in polynomial time. 2. We could also solve NP-complete problems in quantum polynomial time if we were able to separate two exponentially close quantum states in polynomial time. Recall from AL’s state |ali=(2n−s)|0i+s|1i q(2n−s)2+s2 that if we were able to distinguish the cases where s= 0 and s > 0, then we could decide if a Boolean formula is satisfiable or not. However, unitary transformations preserve the angles between states, so it seems that we would not be able to distinguish those two cases using only linear operators. This leads us to talk about our future work on this and related questions. Chapter 3. Quantum mechanics 49 Future work We do not think that we can relax any of the previous assumptions any further while being able to solve NP-complete problems in polynomial time. However, we left an open question during our research that would be interesting to study. That is if we can solve any NP-complete problem in quantum polynomial time using linear operators with unitary eigenvalues. Note that the only difference with unitary operators is that they can be diagonalized orthogonally (for being normal operators), so maybe we can exploit the non-orthogonality of the eigenvectors of linear operators with unitary eigenvalues to separate two exponentially close states in polynomial time, and thus solving SAT in quantum polynomial time. Appendix A. Linear algebra 56 2. For any vectors |vi ∈ V,|w1i,|w2i ∈ Wwe have |vi⊗|w1i+|w2i=|vi⊗|w1i+|vi⊗|w2i. 3. For any vectors |v1i,|v2i ∈ V,|wi ∈ Wwe have |v1i+|v2i⊗|wi=|v1i⊗|wi+|v2i⊗|wi. Let Aand Bbe two linear operators on Vand W, respectively. Then, we can define a linear operator A⊗Bin V⊗Wgiven by (A⊗B)|vi⊗|wi=A|vi⊗B|wi, such that it’s extended to all V⊗Wby linearity. That is, (A⊗B)  k X i=1 αi|vii⊗|wii = k X i=1 αiA|vii⊗B|wii. We can also define an inner product in V⊗Wbased on the inner products defined in Vand Was follows. The inner product of n1 X i=1 αi|vii⊗|wiiand n2 X j=1 βi|˜vji⊗|˜wji is   n1 X i=1 αi|vii⊗|wii, n2 X j=1 βi|˜vji⊗|˜wji = n1 X i=1 n2 X j=1 αiβjhvi|˜vjihwi|˜wji. Proposition A.18. If Aand Bare unitary, self-adjoint, positive-semidefinite or projections, then so is A⊗B. 57 Bibliography [1] Aaronson, S. Reasons to believe. https://www.scottaaronson.com/blog/?p=122. [2] Aaronson, S. Guest Column: NP-complete problems and physical reality. ACM SIGACT News 36, 1 (Mar. 2005), 30–52. [3] Aaronson, S. P =? NP. In Open Problems in Mathematics, J. Nash, John Forbes and M. T. Rassias, Eds. Springer International Publishing, 2016, pp. 1–122. [4] Abrams, D. S., and Lloyd, S. Nonlinear Quantum Mechanics Implies Polynomial-Time Solution for NP-Complete and #P Problems. Physical Review Letters 81, 18 (Nov. 1998), 3992–3995. [5] Arora, S., and Barak, B. Computational Complexity: A Modern Approach, 1st ed. Cambridge University Press, USA, 2009. [6] Baker, T., Gill, J., and Solovay, R. Relativizations of the P =? NP Question. SIAM Journal on Computing 4, 4 (Dec. 1975), 431–442. [7] Bekenstein, J. D. Universal upper bound on the entropy-to-energy ratio for bounded systems. Physical Review D 23, 2 (Jan. 1981), 287–298. [8] Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing 26, 5 (Oct. 1997), 1510–1523. [9] Berger, B., and Leighton, T. Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete. In Proceedings of the second annual international conference on Computational molecular biology (New York, NY, USA, Mar. 1998), RECOMB ’98, Association for Computing Machinery, pp. 30–39. [10] Bringsjord, S., and Taylor, J. P=NP. arXiv:cs/0406056 (June 2004). arXiv: cs/0406056. [11] Buss, S. R. On Gödel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability. In Feasible Mathematics II (Boston, MA, 1995), P. Clote and J. B. Remmel, Eds., Progress in Computer Science and Applied Logic, Birkhäuser, pp. 57–90. [12] Carrillo Redondo, V. 2-dimensional cellular automaton (instantaneous communication assumption), Sept. 2021. https://www.youtube.com/watch?v= 8IIsXnJl7hM. [13] Cook, M. Universality in elementary cellular automata. Complex Systems 15 (2004). [14] Cook, S. The P versus NP problem. In Clay Mathematical Institute; The Millennium Prize Problem (2000). BIBLIOGRAPHY 58 [15] Cook, S. The importance of the P versus NP question. Journal of the ACM 50, 1 (Jan. 2003), 27–29. [16] Cook, S. A. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (New York, NY, USA, May 1971), STOC ’71, Association for Computing Machinery, pp. 151–158. [17] Crescenzi, P., Goldman, D., Papadimitriou, C., Piccolboni, A., and Yannakakis, M. On the Complexity of Protein Folding. Journal of Computational Biology 5, 3 (Jan. 1998), 423–465. [18] Hartmanis, J. Godel, von Neumann and the P=?NP Problem. [19] Johnson, D. J., and Trick, M. A. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society, USA, 1996. [20] Johnson, D. S. A brief history of NP-completeness, 1954–2012. Documenta Mathematica (2012). [21] Margenstern, M., and Morita, K. NP problems are tractable in the space of cellular automata in the hyperbolic plane. Theoretical Computer Science 259, 1 (May 2001), 99–128. [22] Neary, T., and Woods, D. P-completeness of Cellular Automaton Rule 110. In Automata, Languages and Programming (Berlin, Heidelberg, 2006), Lecture Notes in Computer Science, Springer, pp. 132–143. [23] Nielsen, M. A., and Chuang, I. L. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, Cambridge, 2010. [24] Papadimitriou, C. H. Computational Complexity. Addison-Wesley, 1994. [25] Razborov, A. A., and Rudich, S. Natural Proofs. Journal of Computer and System Sciences 55, 1 (Aug. 1997), 24–35. [26] Rieffel, E., and Polak, W. An introduction to quantum computing for non-physicists. ACM Computing Surveys 32, 3 (Sept. 2000), 300–335. [27] Saito, K., Aono, M., and Kasai, S. Amoeba-inspired analog electronic computing system integrating resistance crossbar for solving the travelling salesman problem. Scientific Reports 10, 1 (Nov. 2020), 20772. [28] Schönhage, A. On the power of random access machines. In Automata, Languages and Programming (Berlin, Heidelberg, 1979), H. A. Maurer, Ed., Lecture Notes in Computer Science, Springer, pp. 520–529. [29] Weinberg, S. Testing quantum mechanics. Annals of Physics 194, 2 (Sept. 1989), 336–386. [30] Zhu, L., Kim, S.-J., Hara, M., and Aono, M. Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism. Royal Society Open Science 5, 12 (Dec. 2018), 180396.