Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization

Binary optimization problems with complex non-quadratic objectives or constraints can be reformulated as multi-objective quadratic unconstrained binary optimization (MO-QUBO) problems, which matters because this approach allows complex constraints to be evaluated classically on Pareto-optimal candidates rather than being encoded directly into the quantum model.

The gist: A class of binary optimization problems with complex non-quadratic objectives or constraints can be reformulated as multi-objective quadratic unconstrained binary optimization (MO-QUBO) problems.

Reformulation via Multi-Objective QUBO

The core idea is to reinterpret a constrained problem, which involves maximizing an objective function subject to constraints, as a multi-objective optimization problem. For each feature function, the paper defines a transformed variable: let si ∈ (−1, +1) encode its preferred direction such that the objective and all constraint functions are monotone nondecreasing with respect to the induced dominance order. This leads to defining variables as Zi(x) = sihi(x), i = 1,..., m, resulting in a MO-QUBO: max x∈X Z1(x),..., Zm(x). (2). The reduction relies on the observation that for monotone objectives and constraints, any dominated solution in the transformed feature space can be replaced by a dominating solution without decreasing the objective or worsening feasibility.

Theoretical Guarantee of Global Optimality

Theorem II.1 establishes that if choosing consistent preferred directions for all features is not possible, the reduction assumptions are not met. However, if they are satisfied, at least one globally optimal solution of (1) lies in P (the Pareto set of the MO-QUBO). The proof shows that for any optimal feasible solution x⋆, there exists a dominating Pareto-optimal representative x′ such that Gj(h(x′)) ≥ Gj(h(x⋆)) ≥ 0, ∀j, ensuring that the original problem can be solved by searching the Pareto set of the corresponding MO-QUBO.

Application to Portfolio Optimization under CVaR

The paper demonstrates this framework on binary portfolio optimization under a Conditional Value-at-Risk (CVaR) constraint. Assuming Gaussian returns, the non-quadratic CVaR constraint is transformed into a quadratic form dependent only on two features: expected return and portfolio variance. The MO-QUBO is then constructed using Z1(x) = h1(x) = µT x (expected return) and Z2(x) = −h2(x) = −xT Σx (negative variance). This leads to the MO-QUBO: max x∈X µT x, −xT Σx. (6). The constraint is then evaluated classically using the derived formula: CVaRα(L(x)) = −µT x + κα√xT Σx, (4).

Quantum Approximation and Classical Post-Processing

The approach leverages the Quantum Approximate Multi-Objective Optimization algorithm (QAMOO) to approximate Pareto fronts of the bi-objective QUBO. The overall procedure involves:

1. Constructing the MO-QUBO objectives Z1(x) and Z2(x).

2. Applying QAMOO to obtain candidate portfolios approximating the Pareto set of (6).

3. Classically evaluating the non-quadratic CVaR constraint for each candidate: evaluate the CVaR constraint −µT x + κα√xT Σx ≤ c.

4. Selecting the feasible portfolio with maximum expected return µT x.

Numerical Validation and Performance Metrics

The paper validates this method on a 100-asset instance by comparing QAMOO results against classical solvers like the epsilon-constraint method (ϵ-CM) and discretized weighted-sum methods (WSM). Quality is measured using the hypervolume (HV) indicator, which quantifies how closely the approximation covers the Pareto front. The results show that QAMOO closely approximates reference fronts, achieving high HV values compared to WSM. Specifically, for mean-CVaR fronts at α = 90%, 95%, and 99%, QAMOO reaches between 99.54% and 99.58% of the corresponding ϵ-CM reference HVs. Furthermore, the analysis of expected return gap shows that "RQAMOO(c) > Rϵ-CM(c)" in certain regions, indicating that QAMOO generates a larger set of non-dominated candidates.

Hardware Implementation and Robustness

The implementation utilizes an IBM Quantum computer with QAOA circuits. The training for the QAOA parameters is performed using a linear-ramp (LR) parameterization.

Based on the provided scientific paper, here are specific improvements for AI systems and what those improved systems could achieve:

)AI System Improvements: Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization (QAMOO)

The core improvement lies in shifting the paradigm for solving complex, non-quadratic binary optimization problems from direct penalty encoding to a Pareto set approximation guided by quantum heuristics.

1. (Reformulation and Constraint Handling):

2. (Optimization Strategy):

3. (Application Domain - Portfolio Management):

4. (Generalization and Scalability):

)What the Improved AI System Can Do:

The improved system, leveraging the QAMOO framework, can solve a significantly broader class of real-world optimization problems that are currently intractable for classical binary solvers due to complex constraints or objectives. Specifically:

1. (Robust Portfolio Optimization under Risk Constraints): The system can optimize asset selection (binary decision variables) subject to complex risk metrics like Conditional Value-at-Risk (CVaR) or Value-at-Risk (VaR). Instead of relying on computationally expensive penalty methods, the system uses quantum approximation to map the problem onto a multi-objective QUBO. It then evaluates feasibility against these constraints by checking candidate solutions against the derived mean/risk Pareto front, leading to near-optimal feasible portfolios much faster than traditional methods.

2. (Handling Non-Quadratic Objectives in Binary Settings): The system can tackle problems where the objective function or constraints are non-quadratic (e.g., those depending on higher-order features), provided these functions are monotone with respect to the preferred feature directions. It solves this by reformulating the problem into a Multi-Objective QUBO, allowing complex objectives to be evaluated classically on Pareto-optimal candidates rather than requiring them to be directly encoded in the quantum circuit Hamiltonian.

3. (Heuristic Search for High-Dimensional Combinatorial Problems): For very large, high-dimensional combinatorial problems (like those involving 100+ assets), the system can use QAMOO as a powerful heuristic solver. It approximates the Pareto front of multiple conflicting objectives (e.g., maximizing return while minimizing variance) and then performs a classical post-processing step to select the best solution that satisfies a non-quadratic constraint, effectively navigating vast search spaces by focusing on efficient trade-offs rather than exhaustive search.

4. (Accelerated Risk Analysis): The system can rapidly generate and analyze risk fronts (like Mean-CVaR fronts) for complex financial models. By using QAMOO to approximate the mean-variance front and then filtering through the CVaR constraint, it provides a set of highly robust, feasible solutions across a range of risk bounds, allowing financial analysts to select the optimal portfolio based on specific risk tolerances instantly.

We show that a class of binary optimization problems with complex non-quadratic objectives or constraints can be reformulated as multi-objective quadratic unconstrained binary optimization problems. When the objective and constraints depend on a small number of quadratic features and are monotone with respect to their preferred directions, at least one globally optimal solution lies in the Pareto set of the associated MO-QUBO. This enables the constraints to be evaluated classically on Pareto-optimal candidates rather than encoded as penalties. We demonstrate the approach for binary portfolio optimization under a Conditional Value-at-Risk constraint. Using Quantum Approximate Multi-Objective Optimization on an illustrative 100-asset instance, we approximate the mean-variance Pareto front using an IBM Quantum computer and derive mean-CVaR fronts through classical post-processing. The hardware results recover the overall structure of the classical front and yield near-optimal feasible portfolios for different risk bounds.