(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.
(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.
Discriminating between quantum computing architectures that can provide quantum advantage from those that cannot is of crucial importance.From the fundamental point of view, establishing such a boundary is akin to pinpointing the resources for quantum advantage; from the technological point of view, it is essential for the design of nontrivial quantum computing architectures.Wigner negativity is known to be a necessary resource for computational advantage in several quantum-computing architectures, including those based on continuous variables (CVs).However, it is not a sufficient resource, and it is an open question under which conditions CV circuits displaying Wigner negativity offer the potential for quantum advantage.In this work we identify vast families of circuits that display large, possibly unbounded, Wigner negativity, and yet are classically efficiently simulatable, although they are not recognized as such by previously available theorems.These families of circuits employ bosonic codes based on either translational or rotational symmetries (e.g., Gottesman-Kitaev-Preskill or cat codes) and can include both Gaussian and non-Gaussian gates and measurements.Crucially, within these encodings, the computational basis states are described by intrinsically negative Wigner functions, even though they are stabilizer states if considered as codewords belonging to a finite-dimensional Hilbert space.We derive our results by establishing a link between the simulatability of high-dimensional discrete-variable quantum circuits and bosonic codes.
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!
Continuous-variable bosonic systems stand as prominent candidates for implementing quantum computational tasks. While various necessary criteria have been established to assess their resourcefulness, sufficient conditions have remained elusive. We address this gap by focusing on promoting circuits that are otherwise simulatable to computational universality. The class of simulatable, albeit non-Gaussian, circuits that we consider is composed of Gottesman-Kitaev-Preskill (GKP) states, Gaussian operations, and homodyne measurements. Based on these circuits, we first introduce a general framework for mapping a continuous-variable state into a qubit state. Subsequently, we cast existing maps into this framework, including the modular and stabilizer subsystem decompositions. By combining these findings with established results for discrete-variable systems, we formulate a sufficient condition for achieving universal quantum computation. Leveraging this, we evaluate the computational resourcefulness of a variety of states, including Gaussian states, finite-squeezing GKP states, and cat states. Furthermore, our framework reveals that both the stabilizer subsystem decomposition and the modular subsystem decomposition (of position-symmetric states) can be constructed in terms of simulatable operations. This establishes a robust resource-theoretical foundation for employing these techniques to evaluate the logical content of a generic continuous-variable state, which can be of independent interest. Published by the American Physical Society 2024
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.
All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.
Quantum resource theories identify the features of quantum computers that provide their computational advantage over classical systems. We investigate the resources driving the complexity of classical simulation in the standard model of continuous-variable quantum computing, and their interplay enabling computational universality. Specifically, we uncover a new property in continuous-variable circuits, analogous to coherence in discrete-variable systems, termed , defined as the ability of Gaussian gates to mix position and momentum operators. Using quadrature propagation across multiple computational paths, we develop an efficient classical simulation algorithm for continuous-variable computations with symplectic coherence constant in the size of the circuit. This establishes symplectic coherence as a necessary resource for universality in continuous-variable quantum computing, alongside non-Gaussianity and entanglement. Via the Gottesman-Kitaev-Preskill encoding, we show that the interplay of these three continuous-variable quantum resources mirrors the discrete-variable relationship between coherence, magic, and entanglement.