Day 4 (June 26)

TBA

Optimal placement of Automated External Defibrillators (AEDs) is a large-scale combinatorial problem directly tied to cardiac arrest survival, where each minute of delay reduces survival by 7-10%. Conventional approaches based on the Maximal Covering Location Problem (MCLP) rely on exact solvers that become computationally intractable at the city scale and rarely account for demographic equity. We reformulate AED deployment as a Quadratic Unconstrained Binary Optimization (QUBO) problem and benchmark it across four distinct computational paradigms on a real-world Taipei City testbed comprising 1,458 candidate sites (convenience stores) and up to 12,000 population-weighted demand points.

The coverage probability follows a piecewise distance-decay model: full coverage within 100m, exponential decay up to a service radius of 150m, and zero beyond. Demographic weights encode the elderly population ratio of each candidate's surrounding community, rewarding installations in aging neighborhoods with higher cardiac arrest risk. Following the Ising-QUBO equivalence, all constraints are absorbed as soft quadratic penalties. The objective combines two reward terms, maximizing weighted coverage and demographic equity, with two penalty terms that enforce the installation budget and suppress redundant co-located selections.

Large-scale experiments compare Gurobi MILP against three quantum-inspired solvers, Compal GPU Annealing (CGA), Simulated Quantum Annealing (SQA), Simulated Annealing (SA), and the Fujitsu Digital Annealer (DA3). At the largest instance (12,000 demand points, N=960), Gurobi runtime grows super-linearly to over 9,000s while CGA and DA3 maintain runtimes under 1,000s at comparable coverage (approximately 0.67). SA runtime reaches approximately 2,300s at the same scale, whereas SQA remains below 1,100s but yields slightly lower coverage. Incorporating demographic weighting does not alter solver scaling behavior, confirming that equity is embedded without additional computational overhead.

Small-scale experiments extend the comparison to gate-based QAOA and native quantum annealing hardware. For QAOA, the QUBO is transformed into an Ising Hamiltonian, encoded into a variational circuit with a problem cost operator and a transverse-field mixer, and then optimized over the variational angle parameters. Both CUDA-Q and Qiskit implementations use the same depth (p=1) and hyperparameters. CUDA-Q maintains higher feasibility success rates at mid-range qubit counts (C=9-12: about 50-30%, compared to 20-10% for Qiskit). However, its total runtime reaches around 2,000 seconds at D=36 due to repeated GPU kernel launches during each variational iteration, whereas Qiskit's performance drops earlier because of transpilation overhead. Beyond C=15, both methods decline to about 10-20% success rate, as the global cardinality penalty causes all-to-all couplings that depth-1 circuits can’t reliably enforce. The D-Wave quantum annealer solves these same instances in under a second, achieving a coverage of roughly 0.45 at D=36, comparable to Gurobi and significantly better than both QAOA platforms, showing that native adiabatic hardware already provides practical solution quality where gate-based approaches are limited by circuit expressibility.

This work provides a unified cross-paradigm QUBO benchmark, spanning exact optimization (Gurobi), digital annealing (DA3), quantum-inspired heuristics (CGA, SQA, SA), gate-based QAOA (CUDA-Q, Qiskit), and quantum annealer (D-Wave), on a socially relevant large and small-scale problem, offering concrete cross-paradigm performance evidence for near-term quantum hardware evaluation.

Quantum annealers and related annealing-based methods have attracted considerable attention as promising approximate solvers for combinatorial optimization. A standard formulation for such methods is quadratic unconstrained binary optimization (QUBO). However, many practically important optimization problems, including mixed-binary quadratic programming (MBQP), involve not only binary variables but also continuous variables. To apply annealing-based methods to MBQP, the continuous variables are typically discretized into additional binary variables, which increases the problem size and may degrade approximation quality. This motivates the development of a formulation in which annealing is performed only over the original binary variables.

In this work, we extend the approach proposed in [1] to MBQP. The original framework was developed for constrained binary optimization: it incorporates constraints into the objective via linear relaxation terms and updates the associated Lagrange multipliers by projected gradient steps based on expectation values under the Boltzmann distribution of the induced QUBO. In our extension, the continuous variables can be eliminated analytically, reducing the inner annealing step to a QUBO defined only over the original binary variables. This avoids auxiliary discretization of the continuous sector and makes the resulting formulation well suited to quantum annealers and related annealing-based methods.

Because the algorithm relies on expectation values under a Boltzmann distribution, it is important to understand how the inverse temperature affects its behavior. Moreover, since the constraints are incorporated through relaxation terms, the constraint density can also alter the typical properties of the solution space. To this end, we employ the replica method, a statistical-mechanical approach for analyzing typical-case properties of random systems. In particular, we study how the inverse temperature influences the trade-off between objective quality and constraint satisfaction, and how the constraint density changes the typical solution structure. Finally, we present numerical results on practical instances to evaluate the quality and feasibility of the obtained solutions.

Ising machines, including quantum annealing machines, have attracted attention for solving combinatorial optimization problems. One such application is feature selection in high-dimensional data with a large search space.

We focus on epistasis detection, one of the feature selection problems in genetic data analysis. Given a case-control dataset, where samples are labeled as case (e.g., disease) or control (non-disease), the task is to identify combinations of genetic variables that are associated with the case label through their joint effects. The interaction among the selected genes is referred to as epistasis. Although domain-specific methods such as exhaustive search-based multifactor dimensionality reduction (MDR) [1] are widely used to evaluate such interactions, it becomes computationally infeasible as the interaction order increases.

In a previous study, we defined epistasis detection as a black-box (BB) optimization problem and solved it using factorization machine with quadratic-optimization annealing (FMQA), where the MDR-based classification error is used as the BB function [2]. FMQA is a BB optimization method that uses a factorization machine as a surrogate model and minimizes the FM surrogate output using Ising machines. While the method demonstrated efficient detection of high-order interactions, two practical limitations remained: (i) the use of the full dataset for evaluation, which may lead to overfitting, and (ii) the requirement to fix the interaction order in advance.

To address these issues, we propose an extended FMQA-based method with two key modifications inspired by MDR methodology [3]. First, we introduce cross-validation by partitioning the dataset and evaluating solutions using training data. Second, we perform multi-order optimization by conducting FMQA across different interaction orders and selecting the best solution based on prediction error on the test set.

We evaluated the proposed method using simulated case-control datasets with predefined epistatic interactions of orders 3 to 5. Experimental results show that the method successfully identifies the ground-truth interactions across all tested orders without prior knowledge of the correct interaction order.

This work was conducted in collaboration with Prof. Shu Tanaka from Keio University.

[1] M. D. Ritchie, L. W. Hahn, N. Roodi, L. R. Bailey, W. D. Dupont, F. F. Parl, and J. H. Moore, Am. J. Hum. Genet., vol. 69, pp. 138-147, 2001.

[2] S. Kikuchi and S. Tanaka, arXiv:2601.01860, 2026.

[3] D. Gola, J. M. Mahachie John, K. van Steen, and I. R. Konig, Brief. Bioinform., vol. 17, no. 2, pp. 293-308, 2016.