Georgios Korpas, MSc., Ph.D.

Physics-inspired graph neural networks (PI-GNNs) have been utilized as an efficient unsupervised framework for relaxing combinatorial optimization problems encoded through a specific graph structure and loss, reflecting dependencies between the problem’s variables. While the framework has yielded promising results in various combinatorial problems, we show that the performance of PI-GNNs systematically plummets with an increasing density of the combinatorial problem graphs. Our analysis reveals an interesting phase transition in the PI-GNNs’ training dynamics, associated with degenerate solutions for the denser problems, highlighting a discrepancy between the relaxed, real-valued model outputs and the binary-valued problem solutions. To address the discrepancy, we propose principled alternatives to the naive strategy used in PI-GNNs by building on insights from fuzzy logic and binarized neural networks. Our experiments demonstrate that the portfolio of proposed methods significantly improves the performance of PI-GNNs in increasingly dense settings.

Optimization of constrained quantum control problems powers quantum technologies. This task becomes very difficult when these control problems are nonconvex and plagued with dense local extrema. For such problems, current optimization methods must be repeated many times to find good solutions, each time requiring many simulations of the system. Here, we present quantum control via polynomial optimization (QCPOP), a method that eliminates this problem by directly finding globally optimal solutions. The resulting increase in speed, which can be a thousandfold or more, makes it possible to solve problems that were previously intractable. This remarkable advance is due to global optimization methods recently developed for polynomial functions. We demonstrate the power of this method by showing that it obtains an optimal solution in a single run for a problem in which local extrema are so dense that gradient methods require thousands of runs to reach a similar fidelity. Since QCPOP is able to find the global optimum for quantum control, we expect that it will not only enhance the utility of quantum control by making it much easier to find the necessary protocols, but also provide a key tool for understanding the precise limits of quantum technologies. Finally, we note that the ability to cast quantum control as polynomial optimization resolves an open question regarding the computability of exact solutions to quantum control problems.

Quantum computers have demonstrable ability to solve problems at a scale beyond brute-force classical simulation. Interest in quantum algorithms has developed in many areas, particularly in relation to mathematical optimization - a broad field with links to computer science and physics. In this Review, we aim to give an overview of quantum optimization. Provably exact, provably approximate and heuristic settings are first explained using computational complexity theory, and we highlight where quantum advantage is possible in each context. Then, we outline the core building blocks for quantum optimization algorithms, define prominent problem classes and identify key open questions that should be addressed to advance the field. We underscore the importance of benchmarking by proposing clear metrics alongside suitable optimization problems, for appropriate comparisons with classical optimization techniques, and discuss next steps to accelerate progress towards quantum advantage in optimization. This Review discusses quantum optimization, focusing on the potential of exact, approximate and heuristic methods, core algorithmic building blocks, problem classes and benchmarking metrics. The challenges for quantum optimization are considered, and next steps are suggested for progress towards achieving quantum advantage. Quantum computing is advancing rapidly, and quantum optimization is a promising area of application. Quantum optimization algorithms - whether provably exact, provably approximate or heuristic - offer opportunities to demonstrate quantum advantage. Systematic benchmarking is crucial to guide research, track progress and further advance understanding of quantum optimization. Theoretical research and empirical research using real hardware can complement each other, in the move towards demonstrating quantum advantage.

There has been much recent interest in near-term applications of quantum computers, i.e., using quantum circuits that have short decoherence times due to hardware limitations. Variational quantum algorithms (VQA), wherein an optimization algorithm implemented on a classical computer evaluates a parametrized quantum circuit as an objective function, are a leading framework in this space. An enormous breadth of algorithms in this framework have been proposed for solving a range of problems in machine learning, forecasting, applied physics, and combinatorial optimization, among others. In this paper, we analyze the iteration complexity of VQA, that is, the number of steps that VQA requires until its iterates satisfy a surrogate measure of optimality. We argue that although VQA procedures incorporate algorithms that can, in the idealized case, be modeled as classic procedures in the optimization literature, the particular nature of noise in near-term devices invalidates the claim of applicability of off-the-shelf analyses of these algorithms. Specifically, noise makes the evaluations of the objective function via quantum circuits biased. . Commonly used optimization procedures, such as SPSA and the parameter shift rule, can thus be seen as derivative-free optimization algorithms with biased function evaluations, for which there are currently no iteration complexity guarantees in the literature. We derive the missing guarantees and find that the rate of convergence is unaffected. However, the level of bias contributes unfavorably to both the constant therein, and the asymptotic distance to stationarity, i.e., the more bias, the farther one is guaranteed, at best, to reach a stationary point of the VQA objective.

There has been a great deal of recent interest in binarized neural networks, especially because of their explainability. At the same time, automatic differentiation algorithms such as back-propagation fail for binarized neural networks, which limits their applicability. We show that binarized neural networks admit a tame representation by reformulating the problem of training binarized neural networks as a subadditive dual of a mixed-integer program, which we show to have nice properties. This makes it possible to use the framework of Bolte et al. for implicit differentiation, which offers the possibility for practical implementation of backpropagation in the context of binarized neural networks. This approach could also be used for a broader class of mixed-integer programs, beyond the training of binarized neural networks, as encountered in symbolic approaches to AI and beyond.

Collateral optimization refers to the systematic allocation of financial assets to satisfy obligations or secure transactions while simultaneously minimizing costs and optimizing the usage of available resources. This involves assessing the number of characteristics, such as the cost of funding and quality of the underlying assets to ascertain the optimal collateral quantity to be posted to cover exposure arising from a given transaction or a set of transactions. One of the common objectives is to minimize the cost of collateral required to mitigate the risk associated with a particular transaction or a portfolio of transactions while ensuring sufficient protection for the involved parties. Often, this results in a large-scale combinatorial optimization problem. In this study, we initially present a mixed-integer linear programming formulation for the collateral optimization problem, followed by a quadratic unconstrained binary optimization (QUBO) formulation in order to pave the way toward approaching the problem in a hybrid-quantum and noisy intermediate-scale quantum-ready way. We conduct local computational small-scale tests using various software development kits and discuss the behavior of our formulations as well as the potential for performance enhancements. We find that while the QUBO-based approaches fail to find the global optima in the small-scale experiments, they are reasonably close suggesting their potential for large instances. We further survey the recent literature that proposes alternative ways to attack combinatorial optimization problems suitable for collateral optimization.

We study the effective low energy dynamics of the topologically twisted super Yang-Mills theory on compact four-manifolds that support surface defects where the gauge field becomes singular along certain directions. Following recent work on the topic of u-plane integrals in topological theories, we show that the integrand of the path integral can be expressed in terms of mock modular forms, which allows the evaluation of correlation functions using Stokes' theorem.

We revisit the low-energy effective U(1) action of topologically twisted N = 2 SYM theory with gauge group of rank one on a generic oriented smooth four-manifold X with nontrivial fundamental group. After including a specific new set of Q-exact operators to the known action, we express the integrand of the path integral of the low-energy U(1) theory as an anti-holomorphic derivative. This allows us to use the theory of mock modular forms and indefinite theta functions for the explicit evaluation of correlation functions of the theory, thus facilitating the computations compared to previously used methods. As an explicit check of our results, we compute the path integral for the product ruled surfaces X = Sigma(g) x CP1 for the reduction on either factor and compare the results with existing literature. In the case of reduction on the Riemann surface Sigma(g), via an equivalent topological A-model on CP1, we will be able to express the generating function of genus zero Gromov-Witten invariants of the moduli space of flat rank one connections over Sigma(g) in terms of an indefinite theta function, whence we would be able to make concrete numerical predictions of these enumerative invariants in terms of modular data, thereby allowing us to derive results in enumerative geometry from number theory.