Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
4 results
Search Results
Item Quantum Speedups: Structure, Design, and Application(2023) Wang, Daochen; Childs, Andrew M.; Miller, Carl A.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A quantum speedup occurs when a computational problem can be solved faster on a quantum computer than on a classical computer. This thesis studies the circumstances under which quantum speedups can arise from three perspectives. First, we study the structure of the problem. We characterize how a problem's symmetries decide whether it admits a superpolynomial or polynomial quantum speedup. In particular, we show that the computation of any partial function of a hypergraph's adjacency matrix admits at most a polynomial speedup. Such functions are only weakly symmetric and subsequent work shows that if the symmetry is weakened even further, then a superpolynomial speedup can be possible. To complete the picture for graph problems, we also construct a partial function of a graph's adjacency list that admits an exponential speedup. Second, we study classical paradigms for solving problems. We design a natural quantum query analogue of the divide and conquer paradigm, which we call the ``quantum divide and conquer'' framework. This framework allows us to quantumly speed up the solution of many problems that are classically solved using divide and conquer. The main technical novelty of our framework is that it naturally combines quantum adversary and quantum algorithmic techniques. To showcase its usefulness, we apply it to obtain near-optimal quantum query complexities for four string problems: (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence. Third, we study ways of generalizing a problem known to admit a quantum speedup. We generalize the search problem of finding a marked item in a database to the case where the items are not either marked or unmarked, but are ``partially marked''. The goal is to find the item that is the most heavily marked. We construct a quantum algorithm for this problem within the variable-time framework and prove its near-optimality by modifying the standard adversary method to work for oracles encoding probability distributions. Coincidentally, the problem studied is equivalent to the multi-armed bandits problem in reinforcement learning, which has many applications.Item Excursions at the Interface of Topological Phases of Matter and Quantum Error Correction(2022) Hosseini Lavasani, Seyed Ali; Barkeshli, Maissam; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Topological quantum error-correcting codes are a family of stabilizer codes that are built using a lattice of qubits covering some manifold. The stabilizers of the code are local with respect to the underlying lattice, and logical information is encoded in the non-local degrees of freedom. The locality of stabilizers in these codes makes them especially suitable for experiments. From the condensed matter perspective, their code space corresponds to the ground state subspace of a local Hamiltonian belonging to a non-trivial topological phase of matter. The stabilizers of the code correspond to the Hamiltonian terms, and errors can be thought of as excitations above the ground state subspace. Conversely, one can use fixed point Hamiltonian of a topological phase of matter to define a topological quantum error-correcting code.This close connection has motivated numerous studies which utilize insights from one view- point to address questions in the other. This thesis further explores the possibilities in this di- rection. In the first two chapters, we present novel schemes to implement logical gates, which are motivated by viewing topological quantum error-correcting codes as topological phases of matter. In the third chapter, we show how the quantum error correction perspective could be used to realize robust topological entanglement phases in monitored random quantum circuits. And in the last chapter, we explore the possibility of extending this connection beyond topological quan- tum error-correcting codes. In particular, we introduce an order parameter for detecting k-local non-trivial states, which can be thought of as a generalization of topological states that includes codewords of any quantum error-correcting code.Item Design and Optimization in Near-term Quantum Computation(2021) Bapat, Aniruddha Anand; Gorshkov, Alexey V; Jordan, Stephen P; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum computers have come a long way since conception, and there is still a long way to go before the dream of universal, fault-tolerant computation is realized. In the near term, quantum computers will occupy a middle ground that is popularly known as the “Noisy, Intermediate-Scale Quantum” (or NISQ) regime. The NISQ era represents a transition in the nature of quantum devices from experimental to computational. There is significant interest in engineering NISQ devices and NISQ algorithms in a manner that will guide the development of quantum computation in this regime and into the era of fault-tolerant quantum computing. In this thesis, we study two aspects of near-term quantum computation. The first of these is the design of device architectures, covered in Chapters 2, 3, and 4. We examine different qubit connectivities on the basis of their graph properties, and present numerical and analytical results on the speed at which large entangled states can be created on nearest-neighbor grids and graphs with modular structure. Next, we discuss the problem of permuting qubits among the nodes of the connectivity graph using only local operations, also known as routing. Using a fast quantum primitive to reverse the qubits in a chain, we construct a hybrid, quantum/classical routing algorithm on the chain. We show via rigorous bounds that this approach is faster than any SWAP-based algorithm for the same problem. The second part, which spans the final three chapters, discusses variational algorithms, which are a class of algorithms particularly suited to near-term quantum computation. Two prototypical variational algorithms, quantum adiabatic optimization (QAO) and the quantum approximate optimization algorithm (QAOA), are studied for the difference in their control strategies. We show that on certain crafted problem instances, bang-bang control (QAOA) can be as much as exponentially faster than quasistatic control (QAO). Next, we demonstrate the performance of variational state preparation on an analog quantum simulator based on trapped ions. We show that using classical heuristics that exploit structure in the variational parameter landscape, one can find circuit parameters efficiently in system size as well as circuit depth. In the experiment, we approximate the ground state of a critical Ising model with long-ranged interactions on up to 40 spins. Finally, we study the performance of Local Tensor, a classical heuristic algorithm inspired by QAOA on benchmarking instances of the MaxCut problem, and suggest physically motivated choices for the algorithm hyperparameters that are found to perform well empirically. We also show that our implementation of Local Tensor mimics imaginary-time quantum evolution under the problem Hamiltonian.Item Quantum Thermalization and Localization in a Trapped Ion Quantum Simulator(2016) Smith, Jacob; Monroe, Christopher; Physics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)When a system thermalizes it loses all memory of its initial conditions. Even within a closed quantum system, subsystems usually thermalize using the rest of the system as a heat bath. Exceptions to quantum thermalization have been observed, but typically require inherent symmetries or noninteracting particles in the presence of static disorder. The prediction of many-body localization (MBL), in which disordered quantum systems can fail to thermalize despite strong interactions and high excitation energy, was therefore surprising and has attracted considerable theoretical attention. We experimentally generate MBL states by applying an Ising Hamiltonian with long-range interactions and programmably random disorder to ten spins initialized far from equilibrium with respect to the Hamiltonian. Using experimental and numerical methods we observe the essential signatures of MBL: initial state memory retention, Poissonian distributed many-body energy level spacings, and evidence of long-time entanglement growth. Our platform can be scaled to more spins, where detailed modeling of MBL becomes impossible.