In recent years, immense progress have been made in quantum optimization techniques. In this position paper, we share our opinion on some of the challenges facing the quantum optimization community and highlight opportunities which we believe would benefit from increased attention of researchers.

Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum heuristics for combinatorial optimization. While QAOA has been shown to perform well on small-scale instances and to provide an asymptotic speedup over state-of-the-art classical algorithms for some problems, fault-tolerance is understood to be required to realize this speedup in practice. The low resource requirements of QAOA make it particularly suitable to benchmark on early fault-tolerant quantum computing (EFTQC) hardware. However, the performance of QAOA depends crucially on the choice of the free parameters in the circuit. The task of setting these parameters is complicated in the EFTQC era by the large overheads, which preclude extensive classical optimization. In this paper, we summarize recent advances in parameter setting in QAOA and show that these advancements make EFTQC experiments with QAOA practically viable.

Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. We show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases.

Introducing additional tunable parameters to quantum circuits is a powerful way of improving per-formance without increasing hardware requirements. A recently introduced multiangle extension of the quantum approximate optimization algorithm (ma-QAOA) signifi-cantly improves the solution quality compared with QAOA by allowing the parameters for each term in the Hamilto-nian to vary independently. Prior results suggest, however, considerable redundancy in parameters, the removal of which would reduce the cost of parameter optimization. In this work we show numerically the connection between the problem symmetries and the parameter redundancy by demonstrating that symmetries can be used to reduce the number of parameters used by ma-QAOA without decreasing the solution quality. We study Max-Cut on all 7,565 connected, non-isomorphic 8-node graphs with a nontrivial symmetry group and show numerically that in 67.4% of these graphs, symmetry can be used to reduce the number of parameters with no decrease in the objective, with the average ratio of parameters reduced by 28.1%. Moreover, we show that in 35.9% of the graphs this reduction can be achieved by simply using the largest symmetry. For the graphs where reducing the number of parameters leads to a decrease in the objective, the largest symmetry can be used to reduce the parameter count by 37.1% at the cost of only a 6.1% decrease in the objective. We demonstrate the central role of symmetries by showing that a random parameter reduction strategy leads to much worse performance.

Problems in scientific computing, such as distributing large sparse matrix operations, have analogous formulations as hypergraph partitioning problems. A hypergraph is a generalization of a traditional graph wherein “hyperedges” may connect any number of nodes. As a result, hypergraph partitioning is an NP-Hard problem to both solve or approximate. State-of-the-art algorithms that solve this problem follow the multilevel paradigm, which begins by iteratively “coarsening” the input hypergraph to smaller problem instances that share key structural features. Once identifying an approximate problem that is small enough to be solved directly, that solution can be interpolated and refined to the original problem. While this strategy represents an excellent trade off between quality and running time, it is sensitive to coarsening strategy. In this work we propose using graph embeddings of the initial hypergraph in order to ensure that coarsened problem instances retrain key structural features. Our approach prioritizes coarsening within self-similar regions within the input graph, and leads to significantly improved solution quality across a range of considered hypergraphs.Reproducibility:All source code, plots and experimental data are available athttps://sybrandt.com/2019/partition.

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.

Algorithms for many hypergraph problems, including partitioning, utilize multilevel frameworks to achieve a good trade-off between the performance and the quality of results. In this paper we introduce two novel aggregative coarsening schemes and incorporate them within state-of-the-art hypergraph partitioner Zoltan. Our coarsening schemes are inspired by the algebraic multigrid and stable matching approaches. We demonstrate the effectiveness of the developed schemes as a part of multilevel hypergraph partitioning framework on a wide range of problems.