Session B09: NISQ: Algorithms

Noise-resilient quantum algorithm design for adiabatic quantum computers

We have developed a novel architecture for automated design of quantum adiabatic algorithm by combining deep reinforcement learning and simulation annealing techniques. Through numerical test, we find that our architecture is adaptable for noise-resilient quantum algorithm design, which is of great current demand in the era of noisy intermediate-scale quantum computing. We show that in solving Grover search, our method automatically reaches the optimal performance in terms of time-complexity scaling. Our approach offers a recipe to make the noise-resilient adiabatic quantum computing, and is also generalizable to optimizing quantum simulations.   

Preserving symmetries in NISQ algorithms

Many classical optimization problems display local or global symmetries. In the Quantum Alternating Operator Ansatz (QAOA), these symmetries can be used to design mixers which restrict the evolution of the system to a subspace which is exponentially smaller than the full Hilbert space [1,2]. However, in realistic scenarios, errors can break the symmetry and yield invalid solutions to the optimization problem. In this talk, we show an analysis of the probability of staying in the correct subspace under the influence of realistic noise models. Moreover, for the example of 3-coloring, we show that it is possible to exploit the natural redundancy of the qubit encoding to bring back the evolution into the correct subspace.
[1] From QAOA to QAOA, Hadfield, Wang, O'Gorman, Rieffel, Venturelli, Biswas, Algorithms, 2019.
[2] XY-mixers: analytical and numerical results for QAOA, Wang, Rubin, Dominy, Rieffel, arXiv:1904.09314   

Using Grover's search algorithm to test a three-level quantum system

In the present work, Grover's search algorithm is modified and studied for application to a three-level “qutrit” quantum device. The modified algorithm constructs the superposition of all states via the discrete Fourier transform instead of the standard Hadamard gate. Then, the analogous Grover's diffusion operator is applied m times. The probability of determining the correct answer as a function of m is derived and shown to be very close to unity for specific choices of m. In a real device, the measured probability will deviate from theoretical predictions due to decoherence effects, and, since different energy levels of the qutrit have different decoherence properties, this can potentially affect the performance of the algorithm depending on the marked state. To address these issues, the algorithm has been specifically designed for implementation on the LLNL Quantum Design and Integration Testbed (QuDIT) hardware platform. This device is based on superconducting circuit architecture where the first three-levels of a transmon are used to define the qutrit.   

Utilizing NISQ devices for evaluating quantum algorithms

With the advent of quantum supremacy, we have an unprecedented opportunity to explore quantum algorithms in new ways. The emergence of general-purpose quantum processors opens up empirical exploration of quantum algorithms. Classically, heuristic algorithms, empirically tested on benchmark and real-world problems, work well in practice. With the empirical evaluation NISQ hardware enables, we enter the era of quantum heuristics, where we can expect a broadening of established applications of quantum computing. What to run, and how best to utilize these still limited quantum devices, remain open research questions. We discuss opportunities and challenges for using NISQ devices to evaluate quantum algorithms, including in elucidating quantum computational mechanisms, in designing novel quantum algorithms, in compilation and error-mitigation, and in techniques for evaluating quantum algorithms empirically.
  

What we’ve learned from NISQ application experiments on Sycamore

Does implementing larger and more accurate examples of VQE, QAOA and the like actually teach us anything useful about quantum computing? Or are we wasting our time on refinements of these NISQ favorites if none of them are going to scale to the classically intractable regime without a significant breakthrough? In this talk, I will reflect on these questions in the context of Google’s recent application demonstration experiments on the Sycamore quantum processor.   

Sequential minimal optimization for quantum-classical hybrid algorithms

We propose a sequential minimal optimization method for quantum-classical hybrid algorithms, which converges faster, is robust against statistical error, and is hyperparameter-free. Specifically, the optimization problem of the parameterized quantum circuits is divided into solvable subproblems by considering only a subset of the parameters. In fact, if we choose a single parameter, the cost function becomes a sine curve with period 2π, and hence we can exactly minimize with respect to the chosen parameter. By repeatedly performing this procedure, we can optimize the parameterized quantum circuits so that the cost function becomes as small as possible. We perform numerical simulations and find that the proposed method substantially outperforms the existing optimization algorithms. This accelerates almost all quantum-classical hybrid algorithms readily and would be a key tool for harnessing near-term quantum devices.   

Systematically Improving Quantum Approximate Optimization Algorithm with an Adaptive Ansatz

The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum eigensolver (VQE) algorithm that uses a variational ansatz of an alternating form to minimize a classical (‘problem’) Hamiltonian. The two alternating operators are given by exponentiation of the problem Hamiltonian and by the ‘mixing’ layer, which in the original formulation of QAOA is a rotation of all the qubits about the x axis. It has been discussed in the literature that by using more general mixers the performance of QAOA can be improved. However, determining how to choose these mixers is an open question. Here we provide a solution by employing the recently introduced ADAPT-VQE¹ algorithm, an iterative approach to creating ansatze for VQEs. We show that the performance of QAOA can be improved considerably by allowing more freedom in the single qubit gates and even further by allowing for entangling operations in the mixing layer.

[1] Grimsley, H.R., Economou, S.E., Barnes, E. and Mayhall, N.J., 2019. An adaptive variational algorithm for exact molecular simulations on a quantum computer. Nature communications, 10(1), pp.1-9.   

Bounds on classical simulation of simple quantum models from quantum supremacy.

Quantum simulation is a central application of quantum computing. Quantum supremacy defines systems whose efficient classical simulation is unlikely given complexity-theoretic assumptions. We consider simple physically motivated quantum models that can display quantum supremacy and hence whose efficient simulation by classical means is unlikely. We consider quantum extensions of classical hydrodynamic lattice gas models. We find that the existence of local conserved quantities strongly constrains such extensions. We find the only extensions that retain local conserved quantities correspond to changing the local encoding of a subset of the bits. These models maintain separability of the state throughout the evolution and are thus efficiently classically simulable. We then consider evolution of these models in the case where any of the bits can be encoded and measured in one of two local bases. For quantum extensions of classical models that are computationally universal such quantum extensions can encode Simon’s algorithm and demonstrate quantum supremacy, thus presenting an obstacle to efficient classical simulation.


On Quantum Extensions of Hydrodynamic Lattice Gas Automata Peter Love Condens. Matter 2019, 4(2), 48; https://doi.org/10.3390/condmat4020048   

Maximum weighted independent set and quantum alternating operator ansatz

We study the maximum weighted independent set problem of graph theory using the quantum alternating operator ansatz. We perform simulations on the Rigetti Forrest simulator and analyze the dependence of the algorithm on the depth of the circuit, initial states and the weights of the vertices. We point out that the probability distribution of observation of the feasible states representing maximum independent sets is asymmetric for the Maximum Independent Set problem unlike the MaxCut problem where the probability distribution of feasible states is symmetric. We also give a numerical comparison of the approximation ratios for the algorithm when we choose different initial states in our graph.   

Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers

Solving combinatorial optimization problems on noisy intermediate-scale quantum
(NISQ) devices is currently being advocated for (and restricted to) binary polynomial optimization with equality constraints. This is achieved using, e.g., the variational quantum eigensolver (VQE), a hybrid quantum/classical heuristic approach. We present a decomposition-based approach to extend the applicability of current approaches to mixed binary optimization (MBO) problems, so as to solve a broad class of real-world optimization problems. In the MBO framework, we show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved via variational quantum approaches), and continuous constrained convex subproblems (that can be solved cheaply with classical optimization solvers). The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE on the quantum circuits implemented in Qiskit, an open-source quantum computing software development framework.   

Learning unitaries via gradient descent optimization

We study the learnability of unitary operations within the framework of the quantum alternating operator formalism using gradient descent method. Gradient descent algorithms are first order optimization methods which are of particular interest to the machine learning community due to their greater computational efficiency over second order techniques. However, the manifold of unitaries is non-convex in general and it is well known that gradient descent does not converge to the global minimum in such spaces. This motivates the question of how hard it is to learn a unitary with an alternating operator circuit using gradient descent. In this work, we find that gradient descent requires at least d^2 parameters in an alternating operator sequence to learn an arbitrary unitary in U(d) with a desired accuracy. The rate of convergence rapidly increases when gradient descent is performed in over-parameterized spaces greater than d^2. We heuristically argue the onset of a phase transition when gradient descent is performed on all d^2 parameters to learn a unitary. We present a greedy algorithm that can learn low-depth unitaries with much less than d^2 parameters in an alternating operator sequence. However, the success probability of the greedy algorithm is low.   

Practical demonstration of quantum approximate optimization on Google’s superconducting qubit processor

The quantum approximate optimization algorithm (QAOA) has attracted significant interest as an algorithm suitable for noisy, intermediate-scale quantum (NISQ) computers. QAOA seeks to find approximate ground states of classical Hamiltonians, typically representing binary optimization problems. We demonstrate a practical implementation of QAOA on three problem families at various qubit counts and circuit depths. We show good performance at larger problem sizes and on more complicated problems than has been previously reported. We investigate practical considerations for implementing near-term quantum algorithms. QAOA is a hybrid algorithm involving a classical “outer-loop” optimizer to find optimal parameters. We profile traditional and novel classical outer-loop optimizers to minimize algorithm run-time in a real-world scenario.   

Running large quantum circuits on small quantum computers

With the advent of NISQ computers, the question of running quantum programs whose number of qubits exceeds the capacity of today’s small processors becomes pressing. In this work, we have implemented a recent theoretical proposal [1] consisting in splitting a large circuit into smaller fragments that can be run on smaller processors. As a test case, we have taken circuits used by the quantum approximate approximation algorithm (QAOA [2]) to solve combinatorial optimization problems. We have implemented, run and assessed the method on the IBM Poughkeepsie 20-qubit superconducting quantum processor, and have compared the obtained results with simulations in the presence of noise that we characterized via tomography.

[1] T. Peng, A. Harrow, M. Ozols, and X. Wu, arxiv: 1904.00102 (2019).
[2] E. Farhi, J. Goldstone, and S. Gutmann, arxiv: 1411.4028 (2014).   

Reverse engineering a pairwise entanglement witness for a near-term N-qubit computer

Designing and implementing new and general algorithms for the noisy intermediate scale quantum (NISQ) computers that will soon be available is not easy. In previous work we have suggested, and developed, the idea of using machine learning techniques to train a small quantum system such that the desired process is "learned," thus obviating the algorithm design difficulty. Here, we extend our results towards implementation on NISQ machines. We reverse engineer our learned two-qubit entanglement witness for implementation on Microsoft's Quantum Development Kit and IBM's Quantum Experience; and, using the machine learning technique called "bootstrapping", we infer the pattern for mesoscopic N from simulation results for three-, four-, five-, six-, and seven-qubit systems. The learned witness is robust to noise and decoherence. Our results suggest a fruitful pathway for general quantum computer algorithm design and computation.