Search

Quantum computation promises to advance a wide range of computational tasks. However, current quantum hardware suffers from noise and is too small for error correction. Thus, accurately utilizing noisy quantum computers strongly relies on noise characterization, mitigation, and suppression. Crucially, these methods must also be efficient in terms of their classical and quantum overhead. Here, we efficiently characterize and mitigate crosstalk noise, which is a severe error source in, e.g., cross-resonance based superconducting quantum processors. For crosstalk characterization, we develop a simplified measurement experiment. Furthermore, we analyze the problem of optimal experiment scheduling and solve it for common hardware architectures. After characterization, we mitigate noise in quantum circuits by a noise-aware qubit routing algorithm. Our integer programming algorithm extends previous work on optimized qubit routing by swap insertion. We incorporate the measured crosstalk errors in addition to other, more easily accessible noise data in the objective function. Furthermore, we strengthen the underlying integer linear model by proving a convex hull result about an associated class of polytopes, which has applications beyond this work. We evaluate the proposed method by characterizing crosstalk noise for two chips with up to 127 qubits and leverage the resulting data to improve the approximation ratio of the Quantum Approximate Optimization Algorithm by up to 10 % compared to other established noise-aware routing methods. Our work clearly demonstrates the gains of including noise data when mapping abstract quantum circuits to hardware native ones., Comment: major revision

Compressed sensing is an image reconstruction technique to achieve high-quality results from limited amount of data. In order to achieve this, it utilizes prior knowledge about the samples that shall be reconstructed. Focusing on image reconstruction in nanotomography, this work proposes enhancements by including additional problem-specific knowledge. In more detail, we propose further classes of algebraic inequalities that are added to the compressed sensing model. The first consists in a valid upper bound on the pixel brightness. It only exploits general information about the projections and is thus applicable to a broad range of reconstruction problems. The second class is applicable whenever the sample material is of roughly homogeneous composition. The model favors a constant density and penalizes deviations from it. The resulting mathematical optimization models are algorithmically tractable and can be solved to global optimality by state-of-the-art available implementations of interior point methods. In order to evaluate the novel models, obtained results are compared to existing image reconstruction methods, tested on simulated and experimental data sets. The experimental data comprise one 360{\deg} electron tomography tilt series of a macroporous zeolite particle and one absorption contrast nano X-ray computed tomography (nano-CT) data set of a copper microlattice structure. The enriched models are optimized quickly and show improved reconstruction quality, outperforming the existing models. Promisingly, our approach yields superior reconstruction results, particularly when information about the samples is available for a small number of tilt angles only, Comment: 13 pages, 10 figures

Advancements in mathematical programming have made it possible to efficiently tackle large-scale real-world problems that were deemed intractable just a few decades ago. However, provably optimal solutions may not be accepted due to the perception of optimization software as a black box. Although well understood by scientists, this lacks easy accessibility for practitioners. Hence, we advocate for introducing the explainability of a solution as another evaluation criterion, next to its objective value, which enables us to find trade-off solutions between these two criteria. Explainability is attained by comparing against (not necessarily optimal) solutions that were implemented in similar situations in the past. Thus, solutions are preferred that exhibit similar features. Although we prove that already in simple cases the explainable model is NP-hard, we characterize relevant polynomially solvable cases such as the explainable shortest path problem. Our numerical experiments on both artificial as well as real-world road networks show the resulting Pareto front. It turns out that the cost of enforcing explainability can be very small.

In this work, we propose a robust optimization approach to mitigate the impact of uncertainties in particle precipitation. Our model incorporates partial differential equations, more particular nonlinear and nonlocal population balance equations to describe particle synthesis. The goal of the optimization problem is to design products with desired size distributions. Recognizing the impact of uncertainties, we extend the model to hedge against them. We emphasize the importance of robust protection to ensure the production of high-quality particles. To solve the resulting robust problem, we enhance a novel adaptive bundle framework for nonlinear robust optimization that integrates the exact method of moments approach for solving the population balance equations. Computational experiments performed with the integrated algorithm focus on uncertainties in the total mass of the system as it greatly influence the quality of the resulting product. Using realistic parameter values for quantum dot synthesis, we demonstrate the efficiency of our integrated algorithm. Furthermore, we find that the unprotected process fails to achieve the desired particle characteristics, even for small uncertainties, which highlights the necessity of the robust process. The latter consistently outperforms the unprotected process in quality of the obtained product, in particular in perturbed scenarios.

The recent successes of emerging photovoltaics (PV) such as organic and perovskite solar cells are largely driven by innovations in material science. However, closing the gap to commercialization still requires significant innovation to match contradicting requirements such as performance, longevity and recyclability. The rate of innovation, as of today, is limited by a lack of design principles linking chemical motifs to functional microscopic structures, and by an incapacity to experimentally access microscopic structures from investigating macroscopic device properties. In this work, we envision a layout of a Digital Twin for PV materials aimed at removing both limitations. The layout combines machine learning approaches, as performed in materials acceleration platforms (MAPs), with mathematical models derived from the underlying physics and digital twin concepts from the engineering world. This layout will allow using high-throughput (HT) experimentation in MAPs to improve the parametrization of quantum chemical and solid-state models. In turn, the improved and generalized models can be used to obtain the crucial structural parameters from HT data. HT experimentation will thus yield a detailed understanding of generally valid structure-property relationships, enabling inverse molecular design, that is, predicting the optimal chemical structure and process conditions to build PV devices satisfying a multitude of requirements at the same time. After motivating our proposed layout of the digital twin with causal relationships in material science, we discuss the current state of the enabling technologies, already being able to yield insight from HT data today. We identify open challenges with respect to the multiscale nature of PV materials and the needed volume and diversity of data, and mention promising approaches to address these challenges., Comment: 22 Pages, 6 Figures

Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of $\mathcal{O}(\log T / \sqrt{T})$, where $T$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.

Gamma uncertainty sets have been introduced for adjusting the degree of conservatism of robust counterparts of (discrete) linear programs. The contribution of this paper is a generalization of this approach to (mixed integer) nonlinear optimization programs. We focus on the cases in which the uncertainty is linear or concave but also derive formulations for the general case. By applying reformulation techniques that have been established for nonlinear inequalities under uncertainty, we derive equivalent formulations of the robust counterpart that are not subject to uncertainty. The computational tractability depends on the structure of the functions under uncertainty and the geometry of its uncertainty set. We present cases where the robust counterpart of a nonlinear combinatorial program is solvable with a polynomial number of oracle calls for the underlying nominal program. Furthermore, we present robust counterparts for practical examples, namely for (discrete) linear, quadratic and piecewise linear settings. Keywords: Budget Uncertainty, Discrete Optimization, Combinatorial Optimization

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing realizes, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem or, equivalently, for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of QAOA, a parameterized quantum algorithm, by deriving optimal parameters for special instances which motivates a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

In this work, we present algorithmically tractable safe approximations of distributionally robust optimization (DRO) problems. The considered ambiguity sets can exploit information on moments as well as confidence sets. Typically, reformulation approaches using duality theory need to make strong assumptions on the structure of the underlying constraints, such as convexity in the decisions or concavity in the uncertainty. In contrast, here we present a duality-based reformulation approach for DRO problems, where the objective of the adverserial is allowed to depend on univariate indicator functions. This renders the problem nonlinear and nonconvex. In order to be able to reformulate the semiinfinite constraints nevertheless, an exact reformulation is presented that is approximated by a discretized counterpart. The approximation is realized as a mixed-integer linear problem that yields sufficient conditions for distributional robustness of the original problem. Furthermore, it is proven that with increasingly fine discretizations, the discretized reformulation converges to the original distributionally robust problem. The approach is made concrete for a challenging, fundamental task in particle separation that appears in material design. Computational results for realistic settings show that the safe approximation yields robust solutions of high-quality and can be computed within short time., Comment: 28 pages, 7 figures

In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (arXiv:2106.06446), we formulate the allocation subproblem as a binary program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm. We present numerical results for the integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of gates and output circuit depth when compared to state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods., Comment: Major revision

We study the robust maximum flow problem and the robust maximum flow over time problem where a given number of arcs $\Gamma$ may fail or may be delayed. Two prominent models have been introduced for these problems: either one assigns flow to arcs fulfilling weak flow conservation in any scenario, or one assigns flow to paths where an arc failure or delay affects a whole path. We provide a unifying framework by presenting novel general models, in which we assign flow to subpaths. These models contain the known models as special cases and unify their advantages in order to obtain less conservative robust solutions. We give a thorough analysis with respect to complexity of the general models. In particular, we show that the general models are essentially NP-hard, whereas, e.g. in the static case with $\Gamma = 1$ an optimal solution can be computed in polynomial time. Further, we answer the open question about the complexity of the dynamic path model for $\Gamma = 1$. We also compare the solution quality of the different models. In detail, we show that the general models have better robust optimal values than the known models and we prove bounds on these gaps.