Hybrid quantum-classical algorithms such as the quantum approximate optimization algorithm (QAOA) are considered one of the most promising approaches for leveraging near-term quantum computers for practical applications. Such algorithms are often implemented in a variational form, combining classical optimization methods with a quantum machine to find parameters to maximize performance. The quality of the QAOA solution depends heavily on quality of the parameters produced by the classical optimizer. Moreover, multiple local optima in the space of parameters make it harder for the classical optimizer. In this paper we study the use of a multistart optimization approach within a QAOA framework to improve the performance of quantum machines on important graph clustering problems. We also demonstrate that reusing the optimal parameters from similar problems can improve the performance of classical optimization methods, expanding on similar results for MAXCUT.
Periodicity of the objective function with respect to QAOA parameters, visible on heatmaps in Fig. , has been demonstrated for MAXCUT @cite_33 @cite_20 . The periodicity was also observed for quasi-maximum-likelihood decoding of classical channel codes @cite_3 . This can potentially allow for further restriction of the domain, eliminating some of the local optima and making the optimization problem easier. However, the theoretical results so far are problem specific. Therefore, we restrict our optimization domain to @math , @math , following @cite_34 . Note that this differs from the approach in @cite_56 , where the values of @math and @math were not constrained. A recent result shows that exploiting the periodicity of variational parameters of certain ansatzes for QAOA and other variational algorithms can improve optimization performance @cite_30 .
@cite_30 @cite_33 @cite_3 @cite_56 @cite_34 @cite_20
2924355162 2962767882 2919333331 2901444101 1568345435
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 simple sine curve with period @math , and hence we can exactly minimize with respect to the chosen parameter. Furthermore, even in general cases, the cost function is given by a simple sum of trigonometric functions with certain periods and hence can be minimized by using a classical computer. 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 compare the proposed method with existing gradient-free and gradient-based optimization algorithms. We find that the proposed method substantially outperforms the existing optimization algorithms and converges to a solution almost independent of the initial choice of the parameters. This accelerates almost all quantum-classical hybrid algorithms readily and would be a key tool for harnessing near-term quantum devices. Motivated by the recent advancement of quantum processors, we investigate quantum approximate optimization algorithm (QAOA) to employ quasi-maximum-likelihood (ML) decoding of classical channel codes. QAOA is a hybrid quantum-classical variational algorithm, which is advantageous for the near-term noisy intermediate-scale quantum (NISQ) devices, where the fidelity of quantum gates is limited by noise and decoherence. We first describe how to construct Ising Hamiltonian model to realize quasi-ML decoding with QAOA. For level-1 QAOA, we derive the systematic way to generate theoretical expressions of cost expectation for arbitrary binary linear codes. Focusing on (7, 4) Hamming code as an example, we analyze the impact of the degree distribution in associated generator matrix on the quantum decoding performance. The excellent performance of higher-level QAOA decoding is verified when Pauli rotation angles are optimized through meta-heuristic variational quantum eigensolver (VQE). Furthermore, we demonstrate the QAOA decoding performance in a real quantum device. The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers. We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.