Session X28: Algorithms and Architecture for Quantum Information

Improved implementation of reflection operators

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.   

Vibronic Molecular Spectra on a Universal Quantum Computer

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.   

Quantum Circuit and Algorithm Validation With Prove-It

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.
[1] www.pyproveit.org   

Hamiltonian and Lindbladian Parameter Estimation

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.   

Quantum Computation with Quantum Schur Circuits

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.

A problem supporting this belief was the efficient approximation of matrix elements of the Young orthogonal matrices. While solvable efficiently with PQC, there was no efficient classical algorithm for this task. We give such algorithm by showing that the relevant PQC computation is a quantum Schur circuit and using symmetries of the Schur transformation.

Efficient classical approximation of transition amplitudes however does not mean that the circuits can be also efficiently sampled. We hence prove that quantum Schur sampling circuits with sparse enough output can be sampled from efficiently classically. Numerical study on a small number of qubits shows that a significant fraction of PQC satisfy this condition, allowing for their efficient sampling.   

Disentangling quantum algorithms using symmetry

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.

In this presentation, we will demonstrate how such a reduction could be achieved in a small quantum system using symmetry. In addition to reducing the needed resources, our quantum computer calculations show a significant improvement in accuracy.   

Finding paths with quantum walks

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.   

Machine learning search for quantum algorithms

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.   

Adiabatic Grover's Algorithm and Graph Theory

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.   

Many-Body-Localization Transition in a Universal Quantum Circuit Model

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.   

Intermediate-Scale Full State Quantum Circuit Simulation by Using Lossy Data Compression

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.   

Low-depth parallelization of k-local gates and applications

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.   

Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits

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.   

Quantum Simulation and Optimization in Hot Quantum Networks

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.

arXiv:1809.03794   

Feedback-based simulation of quantum nonlinear dynamics: The Quantum Kicked Top in an ensemble of two-level atoms.

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.