Georgios Korpas, MSc., Ph.D.

Encoding classical data in a quantum state is a key prerequisite of many quantum algorithms. Recently matrix product state (MPS) methods emerged as the most promising approach for constructing shallow quantum circuits approximating input functions, including probability distributions, with only linear number of gates. We derive rigorous asymptotic expansions for the decay of entanglement across bonds in the MPS representation depending on the smoothness of the input function, real or complex. We also consider the dependence of the entanglement on localization properties and function support. Based on these analytical results we construct an improved MPS-based algorithm yielding shallow and accurate encoding quantum circuits. By using Tensor Cross Interpolation we are able to construct utility-scale quantum circuits in a compute- and memory-efficient way. We validate our methods by loading heavy-tailed distributions, including Levy, important in finance, but they apply to any smooth function inputs. We test the performance of the resulting quantum circuits by executing and sampling from them on IBM quantum devices, for up to 156 qubits.

Inspired by the Fleming-Viot stochastic process, we propose a parallel implementation with restart of variational quantum algorithms, with the aim of reducing the time spent by the algorithm in barren plateaus where the optimization direction is unclear. In the Fleming-Viot tradition, parallel searches are called particles. In the proposed approach, the search by a Fleming-Viot particle is stopped when it encounters a region where the gradient is too small or noisy, suggesting a barren plateau area. The stopped particle continues the search after being restarted at another location in the parameter space, potentially taking the exploration away from barren plateaus. We first analyze the behavior of the Fleming-Viot particles from a theoretical standpoint. We show that, when simulated annealing optimization algorithms are used to drive the particles dynamics, the Fleming-Viot system is expected to find the global optimum faster than a single simulated annealing instance. Furthermore, the relative efficiency increases proportionally to the percentage of barren plateaus in the domain. This result is corroborated by numerical experiments carried out on non-convex 2-dimensional synthetic problems, as well as on quantum approximated Max-Cut instances, both in a lower 2-dimensional and a higher 16-dimensional problem. The experiments show that our method tends to perform better than vanilla and parallel simulated annealing when large barren plateaus are present in the domain, especially in the higher-dimensional problem where barrenness tends to be more important.

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.

Causal learning from data has received much attention recently. Bayesian networks can be used to capture causal relationships. There, one recovers a weighted directed acyclic graph in which random variables are represented by vertices, and the weights associated with each edge represent the strengths of the causal relationships between them. This concept is extended to capture dynamic effects by introducing a dependency on past data, which may be captured by the structural equation model. This formalism is utilized in the present contribution to propose a score-based learning algorithm. A mixed-integer quadratic program is formulated and an algorithmic solution proposed, in which the pre-generation of exponentially many acyclicity constraints is avoided by utilizing the so-called branch-and-cut (“lazy constraint”) method. Comparing the novel approach to the state-of-the-art, we show that the proposed approach turns out to produce more accurate results when applied to small and medium-sized synthetic instances containing up to 80 time series. Lastly, two interesting applications in bioscience and finance, to which the method is directly applied, further stress the importance of developing highly accurate, globally convergent solvers that can handle instances of modest size.

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.