Bulletin of the American Physical Society
APS March Meeting 2019
Volume 64, Number 2
Monday–Friday, March 4–8, 2019; Boston, Massachusetts
Session X28: Algorithms and Architecture for Quantum Information |
Hide Abstracts |
Sponsoring Units: DQI Chair: Borja Peropadre, BBN Technology - Massachusetts Room: BCEC 161 |
Friday, March 8, 2019 8:00AM - 8:12AM |
X28.00001: Improved implementation of reflection operators Anirban Narayan Chowdhury, Yigit Subasi, Rolando D Somma Quantum algorithms for diverse problems, including search and optimization problems, require the implementation of a reflection operator over a target state. Commonly, such reflections are approximately implemented using phase estimation. We provide a method that uses a linear combination of unitaries and a version of amplitude amplification to approximate reflection operators over eigenvectors of unitary operators using exponentially less ancillary qubits in terms of the precision of implementing the reflection The gate complexity of our method is comparable to that of the phase estimation approach. We then extend our results to the Hamiltonian case where the target state is an eigenvector of a Hamiltonian whose matrix elements can be queried. Our results are useful in that they reduce the resources required by various quantum algorithms in the literature. Our improvements also rely on an efficient quantum algorithm to prepare a quantum state with Gaussian-like amplitudes that may be of independent interest. We prove a lower bound which shows that the implementation of the reflection operator is optimal in terms of the query complexity. |
Friday, March 8, 2019 8:12AM - 8:24AM |
X28.00002: Vibronic Molecular Spectra on a Universal Quantum Computer Nicolas Sawaya Calculating a molecule’s vibronic spectrum is a hard problem in theoretical chemical physics, as any ground-state vibrational mode can couple to any excited-state mode via the Duschinsky transformation. Though this problem scales combinatorially on a classical computer, researchers have previously proposed an O(M^3) scaling algorithm that solves the vibronic problem using a Boson Sampling Device. With a wholly different approach that uses the quantum phase estimation algorithm in the standard circuit model, we present a quantum algorithm that scales as O(M^2) in both classical and quantum operations, with linear circuit depth. Besides the scaling improvement, we also present methods that allow for substantial reductions of the number of samples collected. Additionally, because our measurement procedure does not destroy the vibronic state, the final state can be used in further computational analyses. Finally, we show how one would include finite temperature effects with a small cost. Our results are relevant to chemical/materials discovery and to the simulation of bosonic systems on a universal quantum computer. |
Friday, March 8, 2019 8:24AM - 8:36AM |
X28.00003: Quantum Circuit and Algorithm Validation With Prove-It Wayne Witzel, Kenneth Rudinger, Robert Carr, Mohan Sarovar Validating algorithm implementations is increasingly important, especially to distinguish implementation mistakes from noise inherent to so-called Noisy Intermediate-Scale Quantum (NISQ) technologies. Debugging a quantum computation is problematic because intermediate states cannot be probed without interfering with the computation. We demonstrate formal quantum algorithm verification using our versatile Python software package called Prove-It [1]. Prove-It is designed to be accessible, convenient, and extensible. It supports unlimited expressivity using LaTeX (including quantum circuit expressions), freedom to add and conveniently track axioms, flexibility to prove theorems independently in any order, and extensible automation capabilities. |
Friday, March 8, 2019 8:36AM - 8:48AM |
X28.00004: Hamiltonian and Lindbladian Parameter Estimation Stefan Krastanov, Sisi Zhou, Steven Flammia, Liang Jiang Estimating the parameters governing the dynamics of a system is a prerequisite for its control. We present a simple but powerful new method to estimate the Hamiltonian (or Lindbladian) governing a quantum system of a few qubits. Our method makes efficient use of all measurements taken of the system and it saturates the information-theoretic limits for such an estimator. Importantly, it is inherently robust to state preparation and measurement errors. It is not limited to evaluating only a fixed set of possible gates, rather it estimates the complete Hamiltonian of the system. The estimator is applicable to any Hamiltonian that can be written as a piecewise-differentiable function and it can easily include estimators for the non-unitary parameters as well. At the heart of our approach is a stochastic gradient descent over the difference between experimental measurement and model prediction. |
Friday, March 8, 2019 8:48AM - 9:00AM |
X28.00005: Quantum Computation with Quantum Schur Circuits Vojtech Havlicek, Sergii Strelchuk, Kristan Temme Many quantum algorithms can be given as reversible classical circuits between a pair of quantum Fourier transformations. Here we study quantum circuits where QFT is substituted by the quantum Schur transform. This is motivated by Permutational Quantum Computing, a restricted computational model believed to capture nonclassical features of quantum computing. |
Friday, March 8, 2019 9:00AM - 9:12AM |
X28.00006: Disentangling quantum algorithms using symmetry Daniel Gunlycke, Sean A Fischer, C Stephen Hellberg, Steven Policastro, Sergio Tafur Quantum entanglement is a natural phenomenon in quantum mechanics that has enormous significance in quantum information science, including quantum computing. It enters quantum states in algorithms through the application of multi-qubit quantum logic operations such as the CNOT and Ising gates. While deliberate entanglement adds power and efficiency to algorithms, unintentional entanglement can be undesirable for a variety of reasons. Unintentional entanglement adds complexity, often making the outcome of a given algorithm more difficult to understand, and potentially more sensitive to errors. Furthermore, it can be an indication that an algorithm has not been optimized. If we could transfer entanglement from our algorithms into the bases that define our systems, then we could potentially reduce our algorithms. Such algorithm reductions will be of outmost importance for resource-limited, noisy intermediate-scale quantum (NISQ) computers. |
Friday, March 8, 2019 9:12AM - 9:24AM |
X28.00007: Finding paths with quantum walks Mark Hillery Quantum walks, which are quantum versions of random walks, have proven useful in the development of quantum algorithms. They have been used to study searches on different graphs. In most cases, the object of the search is a distinguished vertex. However, a quantum walk can find more general objects with a quantum speedup, e.g. extra edges or subgraphs that break the symmetry of the overall graph. They can also find a path from one marked vertex to another, and an example of that will be presented. |
Friday, March 8, 2019 9:24AM - 9:36AM |
X28.00008: Machine learning search for quantum algorithms Jian Lin, Zhong Yuan Lai, Xiaopeng Li Quantum algorithm design lies in the hallmark of applications of quantum computation and quantum simulation. Recent theoretical progress has established complexity-equivalence of circuit and adiabatic quantum algorithms. Here we utilize deep reinforcement learning methods to search for optimal Hamiltonian path in the framework of quantum adiabatic algorithm. We benchmark our approach in Grover search and 3-SAT problems, and find that the adiabatic algorithm obtained by our reinforcement learning approach leads to improved performance in the final state fidelity and significant computational speedups for both moderate and large number of qubits compared to conventional algorithms. Our approach offers a recipe to design quantum algorithms for generic problems through a systematic search. This approach paves a novel way to automated quantum algorithm design by artificial intelligence. |
Friday, March 8, 2019 9:36AM - 9:48AM |
X28.00009: Adiabatic Grover's Algorithm and Graph Theory Samuel Mendelson, Jake Farinholt Adiabatic Grover's Algorithm generally assumes the problem Hamiltonian is diagonal in the computational basis. In this talk, we will show how to reinterpret Grover's search algorithm as a Graph Theory problem, and conversely, we will show how to build the problem Hamiltonian for various graph search problems directly from the Graph Laplacian. Finally, we analyze the performance of the adiabatic algorithms under various graph constraints and provide evidence to suggest that the performance improves with the number of edges. We rigorously prove that the graph search algorithm is exactly Grover's algorithm when the graph is complete. |
Friday, March 8, 2019 9:48AM - 10:00AM |
X28.00010: Many-Body-Localization Transition in a Universal Quantum Circuit Model Adrian Chapman, Akimasa Miyake We develop both exact and approximate methods to compute out-of-time-ordered correlators for arbitrary universal quantum circuits, taking advantage of the mapping of quantum circuits to the dynamics of interacting fermions in one dimension. In this framework, the out-of-time-ordered correlator can be calculated exactly as a superposition of exponentially many Gaussian-fermionic trajectories in the number of interaction gates. We develop a variationally-optimized, Gaussian approximation to the spatial propagation of an initially-local operator by restriction to the fastest-traveling fermionic modes, in a similar spirit as light-front computational methods in quantum field theory. We demonstrate that our method can detect the many-body localization transitions of generally time-dependent dynamics without the need for perturbatively weak interactions. |
Friday, March 8, 2019 10:00AM - 10:12AM |
X28.00011: Intermediate-Scale Full State Quantum Circuit Simulation by Using Lossy Data Compression Xin-Chuan Wu, Sheng Di, Franck Cappello, Hal Finkel, Yuri Alexeev, Fred Chong To develop, evaluate, and validate new quantum algorithms or quantum computers, we need tools to assess their correctness and fidelity. This requires the capabilities of quantum circuit simulation. However, the number of quantum state amplitudes increases exponentially with the number of qubits, leading to the exponential growth of the memory requirement for the simulations. In this work, we present our quantum circuit simulation by using lossy data compression. We simulate quantum circuits by full-state update technique, and the lossy data compression is applied to the quantum state vector. Our preliminary results suggest that we should be able to significantly increase the size of quantum simulations beyond 50 qubits for certain algorithms. |
Friday, March 8, 2019 10:12AM - 10:24AM |
X28.00012: Low-depth parallelization of k-local gates and applications Bryan O'Gorman, William Huggins, Eleanor Rieffel, Birgitta K Whaley Practical use of near-term quantum computers requires taking their limited connectivity into account when realizing quantum circuits. We address this embedding problem for families of quantum circuits defined by a hypergraph where each hyperedge corresponds to a potential gate. We show that any set of k-local gates on n logical qubits can be ordered and parallelized in O(n^{k-1}) depth using a linear arrangement of n physical qubits. The construction is completely general and achieves optimal scaling in the worst case. We demonstrate benefits of this construction for i) sets of mutually commuting gates, as encountered in the Quantum Alternating Operator Ansatz circuits of the generalized QAOA algorithm, and ii) sets of gates that do not commute but for which compilation efficiency is the dominant criterion in their ordering. We find polynomial speedups in cost with number of spin-orbitals and electrons for Trotterized time-evolution of fermionic Hamiltonians under the Jordan-Wigner transformation. |
Friday, March 8, 2019 10:24AM - 10:36AM |
X28.00013: Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits Lucas Kocia, Peter J Love We apply the periodized stationary phase method to discrete Wigner functions of systems with odd prime dimension using results from p-adic number theory. We derive the Wigner-Weyl-Moyal (WWM) formalism with higher order h-bar corrections representing contextual corrections to non-contextual Clifford operations. We characterize the stationary phase critical points as a quantum resource injecting contextuality and show that this resource allows for the replacement of the p^{2t} points that represent t magic state Wigner functions on p-dimensional qudits by ≤ p^{t} points. We find that the π/8 gate introduces the smallest higher order h-bar correction possible, requiring the lowest number of additional critical points compared to the Clifford gates. We then establish a relationship between the stabilizer rank of states and their number of critical points and exploit the stabilizer rank decomposition of two qutrit π/8 gates to develop a classical strong simulation of a single qutrit marginal on t qutrit π/8 gates that are followed by Clifford evolution, and show that this only requires calculating 3^{t/2+1} critical points corresponding to Gauss sums. This outperforms the best alternative qutrit algorithm for any number of π/8 gates to full precision. |
Friday, March 8, 2019 10:36AM - 10:48AM |
X28.00014: Quantum Simulation and Optimization in Hot Quantum Networks Martin Schuetz, Benoit Vermersch, Gerhard Kirchmair, Lieven Vandersypen, Juan Ignacio Cirac, Mikhail Lukin, Peter Zoller We propose and analyze a setup based on (solid-state) qubits coupled to a common multi-mode transmission line, which allows for coherent spin-spin interactions over macroscopic on-chip distances, without any ground-state cooling requirements for the data bus. Our approach allows for the realization of fast deterministic quantum gates between distant qubits, the simulation of quantum spin models with engineered (long-range) interactions, and provides a flexible architecture for the implementation of quantum approximate optimization algorithms. |
Friday, March 8, 2019 10:48AM - 11:00AM |
X28.00015: Feedback-based simulation of quantum nonlinear dynamics: The Quantum Kicked Top in an ensemble of two-level atoms. Manuel H. Muñoz-Arias, Pablo Poggi, Ivan Deutsch We study the implementation of a measurement-based feedback scheme to realize quantum nonlinear dynamics. We specifically study the Quantum Kicked Top (QKT), a standard paradigm of quantum chaos, in the context of an ensemble of spins. The scheme uses a sequence of (not-so) weak measurements of a collective spin variable and global rotations conditioned on the measurement outcome. We show that the resulting dynamics, ensemble averaged over many realizations, is governed by a combination of the QKT Hamiltonian and a non-unitary channel which vanishes in the semiclassical limit, recovering the Classical Kicked Top. We also analyze individual quantum trajectories, where we explore the emergence of chaotic behaviour and revisit the role of the measurement process in the quantum-to-classical transition. |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2023 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700