Since they were first envisioned, quantum computers have oft been portrayed as devices of limitless power, able to perform calculations in a mere instant that would take current computers years to determine. This is, of course, not the case. A huge amount of effort has been invested in trying to understand the limits of quantum computers---under which circumstances they outperform classical computers, how large a speed-up can be gained, and what draws the distinction between quantum and classical computing. In this Ph.D. thesis, I investigate a few intriguing properties of quantum computers involving quantum oracles and classically-simulatable quantum circuits. In Part I I study the notion of black-box unitary operations, and procedures for effecting the inverse operation. Part II looks at how quantum oracles can be used to test properties of probability distributions, and Part III considers classes of quantum circuits that can be simulated efficiently on a classical computer. In more detail, Part I studies procedures for inverting black-box unitary operations. Known techniques are generally limited in some way, often requiring ancilla systems, working only for restricted sets of operators, or simply being too inefficient. We develop a novel procedure without these limitations, and show how it can be applied to lift a requirement of the Solovay-Kitaev theorem, a landmark theorem of quantum compiling. Part II looks at property testing for probability distributions, and in particular considers a special type of access known as the \textit{conditional oracle}. The classical conditional oracle was developed by Canonne et al. in 2015 and subsequently greatly explored. We develop a quantum version of this oracle, and show that it has advantages over the classical process. We use this oracle to develop an algorithm that decides whether or not a mixed state is fully mixed. In Part III we study classically-simulatable quantum circuits in more depth. Two well-known classes are Clifford circuits and matchgate circuits, which we briefly review. Using these as inspiration, we use the Jordan-Wigner transform to develop new classes of non-trivial quantum circuits that are also classically simulatable.
Since they were first envisioned, quantum computers have oft been portrayed as devices of limitless power, able to perform calculations in a mere instant that would take current computers years to determine. This is, of course, not the case. A huge amount of effort has been invested in trying to understand the limits of quantum computers---under which circumstances they outperform classical computers, how large a speed-up can be gained, and what draws the distinction between quantum and classical computing. In this Ph.D. thesis, I investigate a few intriguing properties of quantum computers involving quantum oracles and classically-simulatable quantum circuits. In Part I I study the notion of black-box unitary operations, and procedures for effecting the inverse operation. Part II looks at how quantum oracles can be used to test properties of probability distributions, and Part III considers classes of quantum circuits that can be simulated efficiently on a classical computer. In more detail, Part I studies procedures for inverting black-box unitary operations. Known techniques are generally limited in some way, often requiring ancilla systems, working only for restricted sets of operators, or simply being too inefficient. We develop a novel procedure without these limitations, and show how it can be applied to lift a requirement of the Solovay-Kitaev theorem, a landmark theorem of quantum compiling. Part II looks at property testing for probability distributions, and in particular considers a special type of access known as the \textit{conditional oracle}. The classical conditional oracle was developed by Canonne et al. in 2015 and subsequently greatly explored. We develop a quantum version of this oracle, and show that it has advantages over the classical process. We use this oracle to develop an algorithm that decides whether or not a mixed state is fully mixed. In Part III we study classically-simulatable quantum circuits in more depth. Two well-known classes are Clifford circuits and matchgate circuits, which we briefly review. Using these as inspiration, we use the Jordan-Wigner transform to develop new classes of non-trivial quantum circuits that are also classically simulatable.
The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. On a fundamental level, such an investigation sheds light on the intrinsic computational power that is harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-ups over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. On the other hand, classical simulation of many-body systems is a challenging task, as the dimension of the Hilbert space scales with the number of particles. Therefore, to understand the properties of the systems, suitable approximation methods need to be employed. The lectures will be divided into two parts. In the first part we discuss classical simulation of quantum computation from several perspectives. We review a number of well-known examples of classically simulatable quantum computations, such as the Gottesman-Knill theorem, matchgate simulation and tensor contraction methods. We further discuss simulation methods that are centred on classical sampling methods (‘weak simulation’), and illustrate how these techniques outperform methods that rely on the exact computation of measurement probabilities (‘strong simulation’). The second part focuses on "Entanglement and variational wavefunctions in quantum many body physics". We review the idea of entanglement in quantum many-body systems and how it helps us to understand the success of numerical renormalization group methods. In particular we will discuss a few variational wave-function based methods for simulating strongly correlated quantum systems, which include (1) matrix product states (2) multiscale entanglement renormalization ansatz (3) projected entangled pair states and (4) continuous matrix product states for quantum field theories.
The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. From a fundamental point of view, such an investigation sheds light on the intrinsic computational power harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-up over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. In this talk we discuss novel classical simulation methods that are centered on probabilistic methods ('weak simulation'). We show how these techniques outperform existing methods that rely on the exact computation of measurement probabilities ('strong simulation'). Using weak simulation methods, several new classes of simulatable quantum circuits are generated. For example, we show that various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform an! d other circuits are classically simulatable. Finally, we focus on famous quantum algorithms and investigate the origin of their computational power, or their lack thereof.
(Abridged.) Quantum computers promise to solve some problems exponentially faster than traditional computers, but we still do not fully understand why this is the case. While the most studied model of quantum computation uses qubits, which are the quantum equivalent of a classical bit, an alternative method for building quantum computers is gaining traction. Continuous-variable devices, with their infinite range of measurement outcomes, use systems such as electromagnetic fields. Given this infinite-dimensional structure, combined with the complexities of quantum physics, we are left with a natural question: when are continuous-variable quantum computers more powerful than classical devices? This thesis investigates this question by exploring the boundary of which circuits are classically simulatable and which unlock a quantum advantage over classical computers. A series of proofs are presented demonstrating the efficient simulatability of progressively more complex circuits, even those with high amounts of Wigner negativity. Specifically, circuits initiated with highly Wigner-negative Gottesman-Kitaev-Preskill states, which form a grid-like structure in phase space, can be simulated in polynomial time.
We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp[iθX] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.