Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange

Abstract

Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the second of a two-part tutorial that surveys key elements of Quantum Bridge Analytics and its applications. Part I focused on the Quadratic Unconstrained Binary Optimization (QUBO) model which is presently the most widely applied optimization model in the quantum computing area, and which unifies a rich variety of combinatorial optimization problems. Part II (the present paper) introduces the domain of QUBO-Plus models that enables a larger range of problems to be handled effectively. After illustrating the scope of these QUBO-Plus models with examples, we give special attention to an important instance of these models called the Asset Exchange Problem (AEP). Solutions to the AEP enable market players to identify exchanges of assets that benefit all participants. Such exchanges are generated by a combination of two optimization technologies for this class of QUBO-Plus models, one grounded in network optimization and one based on a new metaheuristic optimization approach called combinatorial chaining. This combination opens the door to expanding the links to quantum computing applications established by QUBO models through the Quantum Bridge Analytics perspective. We show how the modeling and solution capability for the AEP instance of QUBO-Plus models provides a framework for solving a broad range of problems arising in financial, industrial, scientific, and social settings.

1 Introduction

Quantum Bridge Analytics is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the near term and enable enhanced practical application of quantum computing in the future.

As observed in Part I of this tutorial (Glover et al., 2021a, 2022), the Quadratic Unconstrained Binary Optimization (QUBO) model has an important role in Quantum Bridge Analytics by unifying a rich variety of combinatorial optimization problems and becoming at present the most widely applied optimization model in the quantum computing area.

In Part II (the present paper), updated from Glover et al. (2020), we consider applications called QUBO-Plus problems motivated by the classical QUBO formulation that embrace larger classes of problems, and that also make it possible to solve certain subclasses of QUBO problems more effectively. Details of the QUBO-Plus model, including its formulation and illustrative applications, are discussed in Sect. 2.

To underscore the importance of identifying problems that can be treated as QUBO-Plus applications, we give special attention in this paper to a problem class called the Asset Exchange Problem (AEP) which is motivated by developments in blockchains that relate to finding exchanges among investors that are mutually beneficial to all participants. We first describe a QUBO model for a special instance of the AEP and then adopt the QUBO-Plus perspective to consider the relevance of characterizing the AEP domain in a more general form. To further motivate our focus on the AEP we discuss a range of applications both within and beyond blockchains where this class of problems is important. As we demonstrate in the sections that follow, solutions to the AEP enable market players to identify and profit from exchanges of assets that benefit all participants—exchanges that, in game theory terminology, constitute a positive sum game. This provides a mechanism for facilitating exchanges customarily carried out through mechanisms of money, interest, and middlemen by serving instead the blockchain goal of disintermediation to remove or reduce reliance on intermediaries. The resulting modeling and solution process simultaneously afford a link between the applications of classical and quantum computing that are envisioned to be increasingly relevant as the quantum computing area becomes more mature.

We introduce two main hubs for solving AEP models, the first consisting of a mathematical formulation yielding a network optimization model for a basic version of the AEP and the second consisting of a metaheuristic optimization framework called combinatorial chaining that augments the network model to make it possible to derive high quality solutions to more complex instances of the AEP, notably including instances encountered in a wide variety of real world applications.

These developments derive special relevance within the context of Quantum Bridge Analytics, which offers gains by bridging the gap between classical and quantum computational methods and technologies. As observed in the 2019 Consensus Study Report titled Quantum Computing: Progress and Prospects (National Academies, 2019), quantum computing will remain in its infancy for perhaps another decade, and in the interim “formulating an R&D program with the aim of developing commercial applications for near-term quantum computing is critical to the health of the field.” The report further notes that such a program will rely on developing “hybrid classical-quantum techniques.” Innovations that underlie and enable these hybrid classical-quantum techniques, which are the focus of Quantum Bridge Analytics, provide a fertile catalyst for introducing the QUBO-Plus applications in the AEP domain.

Additional links to the Quantum Bridge Analytics theme are provided in Glover et al. (2017, 2021a, 2022) who observe that QUBO and QUBO-Plus models give rise to a variety of formulations for portfolio optimization, and these in turn yield a natural basis for integrating classical and quantum computing via the AEP. Portfolio optimization has a prominent role in the AEP when the assets under consideration involve those customarily incorporated into the portfolio domain. The AEP goes further, both in the portfolio domain and others, by linking the holders of multiple portfolios in a network of cooperative optimization. This establishes a natural alliance with QUBO-Plus models whose solutions identify desirable assets for different participants.

After introducing the general representation of QUBO-Plus models in the next section and providing examples of applications related to the theme of the present paper, in succeeding sections we provide a mathematical optimization model for a basic instance of the AEP and then show how the model can be transformed into a network optimization model, thus laying the foundation for exploiting more complex variants of the AEP.

A note on terminology: we use the term “exchange” rather than “swap” because a swap typically refers to an exchange involving only two items or two participants, and “multiple swaps” refer to a collection of pairwise exchanges, in contrast to an integrated process that requires the coordination among all participants for its execution.

The most developed literature on exchanges occurs for the traveling salesman problem, where the term k-opt refers to an exchange that removes k edges from a tour and replaces them by k other edges so that the resulting configuration continues to be a tour (Hamiltonian cycle; see, e.g., Helsgaun, 2000, 2009). The traveling salesman procedures that come closest to the process of combinatorial chaining are the ejection chain approaches that have been applied to TSPs and other combinatorial optimization problems (Glover, 1996; Rego & Glover, 2006; Rego et al., 2016; Yagiura et al., 2006, 2007).

The blockchain literature refers to exchanges called atomic swaps (also known as cross-chain trading). As elaborated subsequently, these exchanges arise when two parties who want to share their cryptocurrencies execute an exchange by means of Hashed Timelock Contracts (or HTLCs) as a mechanism to make the transaction secure (Fitzpatrick, 2019; Nolan, 2013). Combinatorial chaining makes it possible to generalize these swaps to exchanges involving multiple actors.

Combinatorial chaining and the AEP are to be differentiated from the problem and methods arising in combinatorial auctions where swaps are sought to exchange pairs of buy/sell-orders in futures markets (Müller et al., 2017; Winter et al., 2011). An interesting area for future investigation would be to determine if the combinatorial chaining approach could likewise be applied in the setting of combinatorial auctions to enable auctions involving greater numbers of participants.

The remainder of this paper is organized as follows. Section 2 introduces QUBO-Plus models that provide computationally important alternatives to standard QUBO models. Examples of asset exchange applications are given in Sect. 3 to set the stage for later more extensive and technical discussions. Section 4 provides the fundamental mathematical formulation of the basic AEP problem, and shows how to transform this formulation into a network optimization model. Section 5 characterizes the structure of combinatorial chaining in reference to this basic network model, followed by introducing more advanced processes in Sect. 6 for joining network optimization and combinatorial chaining with metaheuristic analysis to address more complex instances of asset exchanges. The paper concludes with a summary of the key notions and their implications in Sect. 7.

2 QUBO-Plus models and the Asset Exchange Problem

The classical QUBO model is expressed as follows.

$$\mathrm{QUBO}:\;\mathrm{minimize}/\mathrm{maximize} y = {x}^{t}Qx$$

where x is a vector of binary decision variables and Q is a square matrix of constants.

The term “QUBO-Plus” refers to a class of models that augment the preceding standard QUBO representation by introducing important constraints separately from the QUBO model, enabling them to be treated by algorithms specially designed to handle these special constraints. This contrasts with the standard approach that seeks to merge such constraints with the QUBO model by attaching weights to them to create a modified form of the Q matrix as described in the Part I tutorial. Many problems have special constraints that could be modeled in pure QUBO form but may afford advantages from both a computational and “model transparency” point of view by embodying them in a QUBO-Plus model. By keeping these constraints separate from the QUBO formulation, and developing a special algorithm that handles the resulting QUBO-Plus problem, it is possible to solve these problems more efficiently and effectively than by attempting to create a “transformed” QUBO model that folds the constraints into the Q matrix.

Computational studies (Du et al., 2022) document that QUBO-Plus models often deliver superior performance, relative to transformed QUBO alternatives, in terms of solution quality and solution time, and permit larger problems to be solved. Such QUBO-Plus models also provide a transparent reminder of the special constraint(s) that are otherwise lost in a transformed QUBO representation.

While the variety of QUBO-Plus models is substantial and application dependent, we catalog some commonly encountered special cases in the following list. In the cases highlighted below, the reference to setting a variable to 1 can encompass a variety of applications by a correspondence with selecting a particular item from a collection of projects, investments, assets, facilities, locations, buildings, plans, medical treatments, architectural designs, itineraries, etc. In such settings, the special constraint(s) defining the “Plus” component of the QUBO-Plus model embody a key problem feature earmarked for special treatment.

2.1 Common QUBO-Plus model types

• (1) Exact cardinality constrained QUBO problems: requiring an exact number of variables to be set to 1.

• (2) Bounded cardinality constrained QUBO problems: requiring a lower bound and an upper bound on the number of variables set to 1.

• (3) Multi-assignment QUBO problems: requiring disjoint sets of variables to sum to 1.

• (4) Multi-allocation QUBO problems: requiring disjoint sets of variables to sum to specified constants (that may differ from 1).

• (5) QUBO packing problems: requiring sums of variables to be less than or equal to specified constants.

• (6) QUBO covering problems: requiring sums of variables to be greater than or equal to specified constants.

• (7) QUBO problems combining (5) and (6) (also called bounded multi-allocation QUBO problems).

• (8) QUBO knapsack problems: requiring a weighted sum of variables to be less than or equal to a specified constant.

• (9) Multi-knapsack QUBO problems: requiring weighted sums of variables to be less than or equal to specified constants.

• (10) Generalized covering QUBO problems: requiring weighted sums of variables to be greater than or equal to specified constants.

With appropriate modifications, modern QUBO solvers can be customized to produce solutions that satisfy the explicit “Plus” constraints while optimizing the quadratic objective function.

We remark that QUBO-Plus models of type (1) arise naturally in the context of the well-known Maximum Diversity problem and also in portfolio optimization problems where a pre-specified number of assets must be chosen. These models are generalized by those of type (2) which apply to broader settings. QUBO-Plus type (3) models, with their assignment constraints, have many important applications and are further noteworthy for having natural connections to certain types of network problems. In these network-related problems, members of certain groups or sub-groups are assigned to members of other groups with the goal of optimizing some measure that describes the overall effectiveness of the assignments. Problems of this type have a link to the AEP problem via their network-related component.

We describe specific models below that illustrate these connections.

Model 1 While applications of all ten QUBO-Plus type models are found in practice, Type (3) models with their assignment constraints are particularly noteworthy due to their connection to various forms of clustering and applications such models accommodate. Consider for example, an investment setting where ${x}_{ij}=1$ if investor i is assigned to cluster (class of investments) j, and the constraints are $\sum ({x}_{ij}: \mathrm{over all j})=1$ for each investor i ensure that each investor is assigned. A variation of this type of application is where particular investments are assigned to specific investment classes. Each of these applications involves considerations that are relevant to the AEP problem, although they fall short of capturing a variety of additional elements of the AEP as we subsequently indicate.

Model 2 Graph coloring problems present additional applications for QUBO-Plus type (3) models where a color must be assigned to each node in the graph (the assignment constraints) while adjacent nodes are required to receive different colors. The adjacency constraints can be folded into the Q matrix and the node assignment constraints can be imposed traditionally rather than by penalties in the objective function.

The coloring terminology takes on a practical meaning by equating colors with labels used to categorize objects (people, institutions, groups, products, processes, etc.). Nodes that are adjacent (joined by an edge), can be viewed in a context where edges between nodes may be interpreted, for example, to mean that the associated objects are dissimilar, hence a coloring will categorize objects so that dissimilar objects fall in different categories. Minimizing the number of colors results in minimizing the number of categories needed to differentiate the objects. Other interpretations of the adjacency relationship lead to additional applications.

More formally, for a graph G = (V,E) with n vertices,. the Minimum Sum Coloring Problem (MSCP) (Kubicka & Schwenk, 1989) seeks to find a coloring such that the sum of all the colors over all vertices is minimized. If we define ${x}_{ik}=1$ if color k is assigned to vertex i, and we seek a coloring using at most K colors, then the adjacency conditions are satisfied by $x_{ik} + x_{jk} < = 1$ for all $\left( {i,j} \right) \in E$ and all $k \in \left( {1\ldots K} \right).$ For a positive scalar penalty, P, these constraints can be imposed via penalties of the form $Px_{ik} x_{jk}$ to be added to objective function. Proceeding in this fashion yields the penalized objective function:

$$\text{Minimize}\;\sum_{i=1}^{ n}\sum_{k=1}^{K}k ^{\ast} {x}_{ik}+P\left(\sum_{\left(i,j\right)\in E.}{\sum_{k=1}^{K}{x}_{ik}{x}_{jk}}\right)$$

which can be re-written as in the form of $x^{t} Qx.$

Including the node assignment constraints without taking them into the objective function, we have the Minimum Sum Coloring Problem in the following form:

$$\text{Minimize}\;\sum_{i=1}^{ n}\sum_{k=1}^{K}k*{x}_{ik}+P\left(\sum_{\left(i,j\right)\in E.}{\sum_{k=1}^{K}{x}_{ik}{x}_{jk}}\right)$$

subject to

$$\sum_{k=1}^{K}{x}_{ik}=1 \forall i\in \{1\ldots n\}$$

which is a QUBO-Plus model:

$$ {\text{Minimize}}\;x^{t} Qx. $$

subject to

$$\sum_{k=1}^{K}{x}_{ik}=1 \forall i\in \{1\dots n\}$$

Model 3 A practical application involving assignment constraints more closely related to the problems we treat in this paper involves exchanges to re-balance a set of account assignments for account executives in a large organization. For this example, assume that the company in question has K account executives, each responsible for managing a set of accounts. Currently the firm has P > K accounts of varying size in terms of annual revenues. Denote the annual dollar amount of account p by d_p dollars. As business has grown over the past few years, the total dollar amount of business managed by a given account executive has grown in an uneven fashion to produce considerable disparity in the total volume of business managed by a given executive.

To address this issue, top management wants to re-assign accounts to the various account executives to re-balance the system and make the differences in total annual book of business between account executives as small as possible.

This problem can be modeled and solved by a QUBO-Plus model with assignment constraints as follows:

Let ${x}_{pk}=1$ if account p is assigned to executive k; zero otherwise. Then, the total annual volume of business managed by executive k is

$${total}_{k }= \sum_{p=1}^{P}{d}_{p}{x}_{pk}\quad k=1,\dots K$$

Our objective it to make assignments of accounts to executives so that each account gets assigned to an executive while minimizing the squared deviations from one executive to another. That is, our objective function is:

$$\mathrm{min}\;deviation={({total}_{1 }- {total}_{2})}^{2}+ {({total}_{1 }- {total}_{3})}^{2}+\cdots +{({total}_{K-1 }- {total}_{K})}^{2}$$

Substituting the definition of ${total}_{p}$ into the above and writing the objective function in matrix form, we get the QUBO-Plus model with assignment constraints:

$$\begin{aligned} &\text{QUBO-Plus}:\quad \text{Min}\; xQx \\ &\quad\quad\quad\quad\quad\quad\text{st} \\ &\sum_{k=1}^{K}{x}_{pk} = 1 p\in \{1\ldots P\}\end{aligned}$$

where Q is the square, symmetric matrix that results from collecting terms and x is the vector of ${x}_{pk}$ variables relabeled with a single subscript. The constraints ensure that each account gets assigned to one of the executives and the objective function ensures that the differences in total account values from one executive to another are as small as possible. Solving this model will result in a new set of account assignments that re-balance the system.

Our next example illustrates a more general type of application that corresponds to a QUBO-Plus model of type (4), and likewise has features in common with those we address in the AEP problem. In this case, we have selected an application relevant to responding to an outbreak of an epidemic.

Model 4 The goal of this model is to determine an optimal allocation of testing kits, as in the context of virus detection, to a population of n people whose members may or may not be infected. Suppose ${q}_{i}$= the estimated value of having person i tested, and ${q}_{ij}$ = the additional value of having both i and j tested (beyond the value of ${q}_{i}+{q}_{j}$)—as where these individuals interact with different groups of people and it is desirable not to limit testing to those who interact within the same group. The ${q}_{ij}$ coefficients can be made larger if the groups that person i and person j interact with are high risk groups.

The objective is to maximize the total value of the people tested. This can be modeled as a QUBO-Plus problem where the number of people tested equals KitsAvailable, the number of test kits available on a given day.

Define ${x}_{i}=1$ if person i is given the test; 0 otherwise. Then the cardinality constrained QUBO-Plus model is obtained by:

$$ {\text{Maximize\;total\; testing\; value}} = \sum\limits_{i = 1}^{n} {q_{i} x_{i} + \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^{n} {q_{ij} x_{i} x_{j} } } } $$

subject to

$$ \sum\limits_{i = 1}^{n} {x_{i} = {\text{Kits\;available}}} $$

(1)

This basic model incorporating constraint (1) can readily be enriched in a variety of ways. For instance, suppose each person i belongs to a Group k indexed by k = 1,…,K, where members of Group k are identified because they interact or because they are a geographical community or have other features in common considered likely to influence their risk. (These groups may also be identified by a QUBO clustering algorithm.) This results in constraints of the form

$$ \sum\limits_{{i \in I_{k} }} {x_{i} = V_{k} } \;{\text{for k }} = { 1} \ldots {\text{K}} $$

(2)

where ${I}_{k}$ denotes the individuals in group k and ${V}_{k}$ denotes the number of kits to be allocated to group k.

Here the sum of the ${V}_{k}$ values equals KitsAvailable. The ${V}_{k}$ values may be proportional to the sizes of the Groups k or may be skewed by the estimated riskiness of each group as a whole.

The foregoing problem with constraints (1) and (2) is easily formulated as a QUBO problem by taking the constraints into the objective function as illustrated in Part 1 of this tutorial (Glover et al., 2021a), but can be solved more effectively by a special QUBO-Plus algorithm specifically designed for this class of QUBO applications. Constraints (1) and (2) are instances of more general constraints that arise in the AEP problem and are common in many network formulations.

2.2 Differentiation among QUBO-Plus models

In essence, we have three types of QUBO-Plus models. The first type consists of those for which a QUBO formulation can be readily constructed by incorporating certain constraints into the objective function, but the problem can be solved more effectively by a special approach that keeps these constraints separate. The second type consists of a binary choice “logical” problem where a QUBO formulation is exceedingly difficult to construct, yet where again we can develop an effective framework for solving it motivated by the concepts developed for representing and solving QUBO problems. The third type is an extension of the first two, arising in response to practical applications that embody highly exploitable problem structures, such as those in the domain of network-related models which are accompanied by additional combinatorial conditions that take them beyond classical analysis, but that can nevertheless be susceptible to tailored algorithms based on the principles that have produced the most effective QUBO methods.

The first type of QUBO-Plus model is illustrated by the QUBO-Plus formulations above. The second type of model includes problems that have binary network-related formulations, where we can exploit the fact that we can represent basic instances of these problems as QUBO problems and QUBO-Plus problems of the first type. The AEP at the focus of this paper belongs to the third category. We will show that we can capture several essential features of this application within a network optimization model, although one that is exceedingly large and computationally demanding. We will disclose how this structure can alternatively be made susceptible to an approach called combinatorial chaining, where we employ a strategy shared with the most effective QUBO algorithms, which iteratively identifies sub-structures that can be successfully to exploited to yield progressive improvement. A basic (rudimentary) form of combinatorial chaining is presented in Sect. 5 for simpler AEP problem instances. Then in Sect. 6 we describe modifications that give rise to advanced forms of combinatorial chaining that handle more complex AEP formulations.

3 Preliminary examples of the Asset Exchange Problem

As previously intimated, the AEP arises in a variety of contexts, spanning applications in financial investment, resource allocation, economic distribution and collaborative decision making. Our approach to solving this problem is based on a form of cooperative optimization, where multiple parties with complex criteria collaborate as well as compete for resources. This could apply to algorithms for distributing packages between trucks in a delivery network, or dynamic switching to alternative sorting facilities. Or it could apply to collaborative bidding processes for complex multi-criteria contracts or decentralized cooperative group optimization for multi-criteria investment cryptocurrency portfolios. This is quite distinct from traditional portfolio optimization, as with a hedge fund that typically seeks to mitigate risk by diversification with some investments that are negatively correlated.

In the cooperative group optimization setting, our approach generalizes processes that seek atomic exchanges of baskets of fungible tokens or securities by yielding exchanges at a higher combinatorial level. Normally, a financial institution that wishes to execute a large basket of trades, in a way that mitigates execution risk by having an intermediary, can take the basket into its inventory and unwind the trades on its own. Thus, instead of revealing specific information about the assets in the basket, knowledge which could be exploited, the institution and banks can conduct a “zero-knowledge” protocol to effect basket trades. However, this protocol still requires trust in those institutions providing the service. The proposed new approach uses both simple and complex combinatorial exchanges to optimize all parties engaged in the multi-party optimization effort.

The progenitor of such an approach has emerged and is being tested in the cryptocurrency world—this is known as a cross-chain atomic swap. This is where two parties own tokens in separate cryptocurrencies, and want to exchange them without having to trust a third party or a centralized exchange. However, by extending this model and enabling complex multi-party exchanges, splits and aggregations, we can effect full spectrum combinatorial trading to provide trustless algorithmic liquidity without requiring even the normal underlying reserve trading currency.

The simplest instance of such a system is a marketplace of three portfolios. In this market, Portfolio A has asset X and wishes to own some asset Z, Portfolio B has asset Z but wishes to acquire only asset Y, and Portfolio C has asset Y and wishes to own some asset X. In a traditional exchange, participants would exchange what they have for the underlying reserve settlement currency, and then purchase what they want. This would entail two transaction fees per portfolio. Alternatively, using cross chain atomic swaps, the parties would never make any transactions whatsoever, as the global optimal cannot be reached via pairwise swap transactions.

By enabling all potential complex exchanges, splits and aggregations, for N portfolios, any market could increase its global utility. However, the computational complexity of this type of complex combinatorial exchange trading is NP-complete. By using a multi-attribute trade matching system that includes the unspoken goals of the parties, which are the “utility functions” of the parties, it is possible to find Pareto-efficient exchange solutions—referring to the game theory concept of a strategy that cannot be made to perform better against one opposing strategy without performing less well against another.

Additionally, the inclusion of constraints increases the complexity of the problem. For example, if the system determines that diversification is required, then a constraint can be added that limits which types of assets could be included in the diversification target. Only assets that have been rated by a rating agency or analyst, for example, as better than a “B” rating, could be included to modify the optimization. A continuous approach would assign each rating a numerical value, and blend that with volatility metrics, volume data, social impact scores, and even the user’s personal pet peeves—to enable a multi-objective approach to optimize both individual and multiple portfolios.

In the future, the user will require the ability to enter or modify both market orders (with fixed prices) and limit orders (with variable prices). As we transition from market orders to limit orders, this will help to expand utility expression, and it can become appropriate to add constraints to help identify price improvement opportunities—allowing a combinatorial exchange to operate for a share of price improvement, rather than charging transaction fees. Just as Bitcoin promises “zero cost transactions”, this could provide a model for “zero cost exchanges” that provide the appearance of negative transaction cost given a disparity of utility functions. In Sect. 6 we discuss the use of priorities to address such considerations.

The current model for the most effective form of exchange is the double-sided exchange, a system in which both buyers and sellers provide bids for matching via the exchange. A central controlling system matches the sell bids with the buy bids, yielding matched buy bids and matched sell bids in response thereto so that allocations of the matched buy bids and the matched sell bids maximize the throughput of the exchange. Combinatorial exchanges using cooperative optimization could potentially lay a foundation for the next evolutionary step in market exchange protocols, moving from double sided trading using a reserve currency to something more general that encompasses new forms of economic transactions.

Double sided exchanges are used to trade goods, services, or other things of value, including network bandwidth trading, financial-instruments trading, transportation logistics, pollution-credit trading, electric power allocation, and so on. However, to make double sided exchanges work, they require fungibility. And so, varying levels of quality, that describe for example the quality of crude oil, are lumped into fungible categories of sulfur content, gravity, etc. This further suggests the possibility that combinatorial exchanges could reflect multi-attribute trading more effectively, allowing traders to work with greater accuracy in pricing.

Combinatorial exchanges can likewise be used for handling non-fungible assets. As long as people are willing to assign value to objects to be traded, combinatorial exchanges can provide a basis to get people what they want. Suppose User A wants to sell a vacation timeshare he or she is tired of, for a certain collectible car with roughly the same value. There are no matches as both are relatively illiquid markets and it could take several months or require a significant discount to find buyers. However, there could be a User B who has exactly the car A wants, but doesn’t want a timeshare, and instead wants a diamond necklace. Now if there is a jeweler C who would find that timeshare exciting, and willing to create a custom necklace to B’s liking, the system could enable algorithmic liquidity by joining all three into a complex transaction.

Moving toward a more general example, A and B’s assets most likely have different values. If there is no jeweler willing to make just the right necklace, the value exchange would not add up. Two parties would likely need to add or accept part of the value in cash. However, with the inclusion of a special user D, who is willing to inject cash and accept a partial tokenized share of that collectible car or real estate, the complex transaction becomes possible. We call this special user a “decentralized market maker” who would require a modest premium to compensate for enabling greater liquidity. That token share could be sold at a later time, hence it is an offer to sell cash for time.

Additional connections to blockchains via decentralized market making are described in Appendix 1.

One last note concerns the potential for quantum computing in this arena. In general, present day quantum computers can handle only a very limited number of qubits, representing a small number of asset types, or cooperating portfolios. When quantum computers can offer hundreds of thousands of qubits, with effective partitioning algorithms, combinatorial exchanges will be able to scale to manage real world liquidity needs for applications involving massive numbers of participants and classes of items to exchange. Until then, quantum computing will enable exchange functionality for only limited and constrained markets, such as for cryptocurrencies. For example, a crypto wallet that holds only a dozen types of crypto would represent a relatively small variable space and could potentially be optimized using a quantum computer. Money was invented to simplify barter, and a quantum exchange based on Pareto-efficient combinatorial exchanges could simplify money.

As noted in Part I, the QUBO model has been adopted as a central focus by the quantum computing community, and by groups that aspire to solve problems by emulating quantum computation with classical hardware. Motivated by the Quantum Bridge Analytics perspective we can enlarge this focus to embrace QUBO-Plus models, and in particular those of the third type discussed in Sect. 2.2. As we will show, this enables us to provide the desired exchanges by identifying combinatorial chaining algorithms that are capable of accommodating variable spaces for AEP models of significantly greater dimension, providing advances in the near term that can be translated into progressively greater advances in the future as quantum computing technology becomes more mature.

4 Mathematical formulations of the AEP

The AEP has several levels. We start from the most basic level of the AEP, which we call AEP0, defined in reference to a graph G = (N, E), with node set N = {1, …, n} and edge set E = {{i,j}, i, j ∈ N} ⊂ N × N. Each node i ∈ N identifies an entity such as an individual or business or institution, and each edge {i,j} identifies an exchange link between i and j. Let A denote the set of asset types (classes), where elements α ∈ A can represent classes of tokens in a cryptocurrency application or types of securities in a securities market or categories of commodities in a commodity market, and so forth. In the following we use the term assets interchangeably with the term asset types.

In AEP0, each node i ∈ N has a set S_i of assets it can send (i.e., can agree to send) to other nodes and a set R_i of assets it can receive (i.e., can agree to receive) from other nodes. Thus, for example, if α′ ∈ S_i and α″ ∈ R_i, then node i can agree to send asset α' and agree to receive asset α" from other nodes. More precisely, R_i denotes assets that i desires (considers beneficial) to receive and S_i denotes assets that i is willing to send (in return for obtaining an asset in the set R_i). We say a transfer of asset α from node i to node j is admissible if α ∈ S_i and α ∈ R_j (α ∈ S_i ∩ R_j). We allow only admissible transfers in seeking asset exchanges that benefit all participants.

Define N_i = {j ∈ N: {i,j} ∈ E} to be the set of nodes j that are neighbors of node i (i.e., that join node i by an edge). Let x_ij^α denote the number of units of asset α transferred from node i to node j. In restricting consideration to admissible transfers, we assume each node i has an upper limit U_i^α:R on the number of units of any given asset α ∈ R_i that can be admissibly transferred from other nodes to node i and an upper limit U_i^α:S on the number of units of α ∈ S_i that can be transferred from i to other nodes. Formally, these conditions may be expressed as

$$ \sum ({\text{x}}_{{{\text{ji}}}}^{\alpha } :{\text{ j}} \in {\text{N}}_{{\text{i}}} ) \le {\text{ U}}_{{\text{i}}}^{{\alpha :{\text{R}}}}\quad {\text{i}} \in \text{N}\;\text{and} \;\alpha \in {\text{R}}_{{\text{i}}} $$

(3)

$$ \sum ({\text{x}}_{{{\text{ij}}}}^{\alpha } :{\text{ j}} \in {\text{N}}_{{\text{i}}} ) \, \le {\text{ U}}_{{\text{i}}}^{{\alpha :{\text{S}}}} \quad {\text{i}} \in {\text{N}}\;\text{and} \;\alpha \in {\text{S}}_{{\text{i}}} $$

(4)

We also impose an equation that requires the total number of assets transferred from a given node i to other nodes j to equal the total number of assets transferred in return from other nodes j to node i. Specifically, for a given node i ∈ N, we observe that the quantity ∑(x_ij^α: α ∈ S_i ∩ R_j and j ∈ N_i) identifies the total number of units that can be admissibly transferred from node i to all nodes j and similarly, the quantity ∑(x_ji^α: α ∈ S_j ∩ R_i and j ∈ N_i) identifies the total number of units that can be admissibly transferred from all nodes j to node i. We require these two quantities to be equal by stipulating

$$ \sum ({\text{x}}_{{{\text{ij}}}}^{\alpha } :\alpha \in {\text{S}}_{{\text{i}}} \cap {\text{R}}_{{\text{j}}} \;{\text{and\;j}} \in {\text{N}}_{{\text{i}}} ) = \sum ({\text{x}}_{{{\text{ji}}}}^{\alpha } :\alpha \in {\text{S}}_{{\text{j}}} \cap {\text{R}}_{{\text{i}}} \;{\text{and j}} \in {\text{N}}_{{\text{i}}} )\; {\text{i}} \in {\text{N}} $$

(5)

Finally, we impose an additional limit U_i on the number of all assets α that can be admissibly transferred from node i to other nodes, expressed as

$$ \sum ({\text{x}}_{{{\text{ij}}}}^{\alpha } :\alpha \in {\text{S}}_{{\text{i}}} \cap {\text{R}}_{{\text{j}}} \;{\text{and\;j}} \in {\text{N}}_{{\text{i}}} ) \, \le {\text{ U}}_{{\text{i}}} {\text{i}} \in {\text{N}} $$

(6)

As a result of Eq. (5), this inequality is equivalent to

$$ \sum ({\text{x}}_{{{\text{ji}}}}^{\alpha } :\alpha \in {\text{S}}_{{\text{j}}} \cap {\text{R}}_{{\text{i}}} \;{\text{and j}} \in {\text{N}}_{{\text{i}}} ) \le {\text{ U}}_{{\text{i}}} {\text{i}} \in {\text{N}} $$

(7)

Subject to these conditions, in problem AEP0 we seek to maximize the total number of admissible exchanges, hence yielding the formulation

$$ \begin{aligned} {\text{Maximize}} & \, \sum ({\text{x}}_{{{\text{ij}}}}^{\alpha } : {\text{i}} \in {\text{N}},{\text{ j}} \in {\text{N}}_{{\text{i}}} ,\alpha \in {\text{S}}_{{\text{i}}} \cap {\text{R}}_{{\text{j}}} ) \\ {\text{subject to}} & \;{(3)},{ (4)}, {(5)}, {\text{(6)\; and \; x}}_{{{\text{ij}}}}^{\alpha } \ge 0,{\text{ i}} \in {\text{N}},{\text{ j}} \in {\text{N}}_{{\text{i}}} \;{\text{and }}\;\alpha \in {\text{S}}_{{\text{i}}} \cap {\text{R}}_{{\text{j}}} \\ \end{aligned} $$

(8)

We can also replace (8) by a variety of other objectives, such as

$$ {\text{Maximize }}\sum ({\text{p}}_{{\text{i}}}^{\alpha } {\text{x}}_{{{\text{ij}}}}^{\alpha } : {\text{i}} \in {\text{N}},{\text{ j}} \in {\text{N}}_{{\text{i}}} ,\alpha \in {\text{S}}_{{\text{i}}} \cap {\text{R}}_{{\text{j}}} ) $$

(9)

where p_i^α is a positive monetary value that node i attaches to receiving asset α from the set R_i.

We now take the step of transforming the foregoing preliminary AEP0 formulation into a network optimization formulation. Under the assumption that the data are integers, this allows us to automatically obtain solutions where the variables receive integer values when an extreme point network algorithm is used. More broadly, it gives a foundation for generating solutions to the AEP0 model by a corresponding basic version of our combinatorial chaining approach. From this, we will be able to treat related more complex AEP models by natural extensions that combine the network optimization and combinatorial chaining components. The transformation of AEP0 to a network formulation significantly increases the problem size, but offsets this by making the problem sparser, while our combinatorial chaining algorithm for this formulation is able to work with a memory based on the number of nodes rather than the number of arcs in the network, dramatically reducing both the amount of computation and the memory involved.

4.1 Transforming AEP0 to a network formulation

The transformation of AEP0 to an equivalent network formulation, which we call NetAEP0, arises by replacing the graph G by a graph G* = G*(N*, A*) consisting of a set of nodes N* and a set of arcs (directed edges) A* as follows.

To emphasize the arc orientation in creating G*, we find it useful to augment the customary representation of an arc from a node p to a node q as an ordered pair (p, q) by alternatively writing it in the form p → q, which adds clarity when p and/or q is itself represented as an ordered pair. Lower bounds on all arc flows are assumed to be 0.

To generate G*, we divide each node i ∈ N into two nodes, i[R] and i[S], and create an arc i[R] → i[S]. In addition, for each i ∈ N and α ∈ R_i we create new nodes (α, i[R]), producing ∑(|R_i|: i ∈ N) nodes, and create arcs (α, i[R]) → i[R] (from node (α, i[R]) to node i[R]) which results in ∑(|R_i|: i ∈ N) arcs (the same as the number of nodes (α, i[R])). Similarly, for each i ∈ N and α ∈ S_i we create new nodes (α, i[S]), producing ∑(|S_i|: i ∈ N) nodes, and create arcs i[S] → (α, i[S]), creating ∑(|S_i|: i ∈ N) arcs (the same as the number of nodes (α, i[S])). If α ∈ R_i, we assume there is at least one neighbor of node i that can receive the asset α, or else we can drop α from R_i. Similarly, if α ∈ S_i, we assume there is at least one neighbor of node i that can send α or else we can remove α from S_i. If, as a result of these removals, either R_i or S_i becomes empty, we can remove node i from N.

Finally, for each i ∈ N and for each j ∈ N_i and for each α ∈ S_i ∩ R_j, each node (α, i[S]) joins by an arc (α, i[S]) → (α, j[R]) to node (α, j[R]). We call these the α-linking arcs of G*, since the same asset α is referenced by both nodes of each of these arcs. The number of these arcs is ∑(| S_i ∩ R_j|: i ∈ N, j ∈ N_i).

From this construction we see that N* consists of 2n + ∑(|R_i| + |S_i|: i ∈ N) nodes and A* contains n + ∑(|R_i| + |S_i|: i ∈ N) + ∑(|S_i ∩ R_j|: i ∈ N, j ∈ N_i) arcs.

To create NetAEP0 from G*, we introduce flows on the arcs governed by bounds as follows. Each arc i[R] → i[S] receives an upper bound on its flow of U_i from (6). Correspondingly, each of the (α, i[R]) → i[R] arcs receives an upper bound on its flow of U_i^α:R from (3) and each of the arcs i[S] → (α, i[S]) receives an upper bound on its flow of U_i^α:S from (4). Finally, the α-linking arcs of G* are not given upper bounds (i.e., their upper bounds may be treated as infinity). All lower bounds are implicitly 0.

It is assumed that U_i satisfies U_i ≤ Min(∑(U_i^α:R: α ∈ R_i), ∑(U_i^α:S: α ∈ S_i)), that is, the upper bound U_i on the flow across arc i[R] → i[S] is limited by the smaller of the sum of upper bounds on the arcs (α, i[R]) → i[R] entering i[R] and the sum of upper bounds on the arcs i[S] → (α, i[S]) leaving i[S]. (Later we also describe variations in which we additionally introduce lower bounds L_i^α:R and/or L_i^α:S on the arcs (α, i[R]) → i[R] and arcs i[S] → (α, i[S]).)

Because we start from the symmetric graph G in undirected edges to produce the graph G* with directed arcs underlying NetAEP0, j ∈ N_i implies i ∈ N_j. We additionally observe that no asset α is contained in both R_i and S_i for any given i, under the assumption that if node i sees a benefit in receiving a unit of α ∈ R_i, then it will not be willing to relinquish a unit of α by including it in S_i. Exceptions can be imagined, as where i may be willing to give up a particular α' ∈ R_i if it is able to receive a more highly valued asset α″ ∈ R_i. Such exceptions can be modeled by extensions of the constructions used here but make the formulation larger and more complex. Nevertheless, our basic algorithm can be modified to handle these and other variations without entailing the complexity introduced by an extended mathematical formulation.

The foregoing description of G* and the conditions defining NetAEP0 can be translated into an algorithm for generating the network. As part of this we show how to attach numerical indexes denoted by k = 1 to n* to the nodes in N* so that NetAEP0 may be represented as a network in a standard format. We refer to lower bounds as well as upper bounds on arcs for generality, although in direct transformation of AEP0 to NetAEP0 the lower bounds will be 0.

4.2 Algorithm to generate NetAEP0

Costs or profits may be attached to the arcs of the network NetAEP0 according to the objective that is desired to be achieved. Asset arcs, which are linking arcs, should be assigned a 0 cost or profit.

An illustration of the structure of NetAEP0 is given in Appendix 2.

5 Basic version of combinatorial chaining

A classical theorem of network flows (Fulkerson & Ford, 1962) implies that a feasible solution to NetAEP0 can be decomposed into a sum of incidence vectors of cycles (not necessarily disjoint or uniquely determined). Such cycles are of interest for the AEP in both its simpler AEP0 form and its more complex forms because they identify a collection of participants who can enter into a succession of mutually beneficial asset exchanges. Such a collection is not unduly difficult to identify by reference to a solution to the NetAEP0 formulation but requires additional effort. Fulkerson and Ford’s max flow algorithm would automatically identify (augmenting) paths from source to sink in the network, which has some similarity with combinatorial chaining. But a standard network flow algorithm for solving NetAEP0 is not capable of being directly adapted to provide good solutions to more complex variations of the AEP that abound in practical applications, thus motivating the creation of the adaptive combinatorial chaining approach.

Adopting the netform perspective (Glover et al., 1992), combinatorial chaining is designed both to exploit the structure of the basic AEP network formulation and to be susceptible to extensions for solving a variety of AEP variations found in practice. This harmonizes with the Quantum Bridge Analytics perspective as in applications where quantum computing can be applied to solve portfolio optimization problems expressed as QUBO models for individual investors or institutions, and more generally leads to consideration of a QUBO-Plus formulation of the third type. Combinatorial chaining can then be applied to the appropriate AEP variation to integrate and improve these individual solutions to the benefit of each participant.

The strategy underlying the basic form of combinatorial chaining operates by generating successions of directed trees (or arborescences in graph theory) rooted at different nodes. Conditions are monitored to disclose when a directed tree can be extended by connecting a tip of one of its branches to the root, thus creating a cycle that constitutes a mutually beneficial exchange. The process differs from classical tree generation algorithms by introducing multiple categories of tree predecessors and establishing a mechanism to trace the predecessors that differentiates between the categories effectively. This introduction of multiple categories of tree predecessors and mechanisms for tracing them likewise causes our method to operate differently from classical min cost flow algorithms based on generating augmented paths (Barr et al., 1978; Glover et al., 1986). This departure from classical approaches arises because many of the more general AEP models belong to the class of multi-commodity network flow problems (Assad, 1978; Hu, 1963), which are more complex than standard “pure” network flow problems, and normally cannot be transformed into a pure network problem as we have accomplished for AEP0. Rather than being a disadvantage, however, this complexity enables the chaining mechanism to be adapted to AEP variations beyond AEP0.

More broadly, the combinatorial chaining mechanism we employ is closely related to the ejection chain procedures for combinatorial optimization noted in Sect. 1. In its more advanced forms outlined in Sect. 6, it is additionally related to the path relinking approaches that are joined with ejection chains in Yagiura et al., (2006, 2007) and that produce the leading methods for the QUBO problem in Resende et al. (2010), Wang et al. (2012), Samorani et al. (2019) and Glover et al., (2020, 2021b).

5.1 Rudimentary combinatorial chaining for the NetAEP0 model

Combinatorial chaining for the basic NetAEP0 model makes use of arrays denoted FlowR(α, i[R]) to record flows on the arcs (α, i[R]) → i[R] and arrays denoted FlowS(α, i[S]) to record the flows on the arcs i[S] → (α, i[S]). Hence, for each i ∈ N, we require FlowR(α, i[R]) ≤ U_i^α:R for each α ∈ R_i, and require FlowS(α, i[S]) ≤ U_i^α:S for each α ∈ S_i. Flows on the arcs arc i[R] → i[S] are recorded in an array Flow(i) for each i ∈ N. All flow values are initialized to 0.

It is convenient to refer to the nodes (α, i[R]), (α, i[S]) and i (the latter collectively representing the two nodes i[R] and i[S]) as open when their associated flows FlowR(α, i[R]), FlowS(α, i[S]) and Flow(i) do not reach their upper bounds and closed otherwise. (A bit can be set for each such node to determine its open/closed status.)

We refer to two types of predecessor arrays PredR(i) and PredS(i), i ∈ N, accompanied by associated arrays AssetR(i) and AssetS(i) explained subsequently. The arrays PredR(i) and PredS(i) are initialized to 0 to indicate predecessors are not yet assigned.

The method performs forward scans and reverse scans to examine nodes i ∈ N (and from there to examine the arcs these nodes can become linked to in a chain). When a tip of the tree can successfully be linked to the root, a breakthrough occurs by establishing the existence of an exchange cycle that is mutually beneficial for all its participants. Breakthrough is accompanied by appropriately updating (increasing) the flows on arcs of the cycle.

The basic version of the chaining algorithm only performs forward scans but gives the foundation for performing reverse scans as well, as subsequently described. We first explain the nature of the forward scan routine and then give a more formal description.

5.1.1 Rationale of the Forward Scan Routine

The Forward Scan Routine is embedded in a Main Routine that maintains a set N^o identifying the open nodes, initialized by N^o = N. Nodes to be scanned are placed in a set denoted ScanSet that begins with a chosen node i* ∈ N^o. During the Forward Scan Routine, ScanSet acquires other nodes i ∈ N^o to form a tree that yields a collection of chains rooted at node i*. The tree is generated by successively selecting new nodes i from ScanSet as long as ScanSet ≠ ∅.

For each node i selected from ScanSet, consider each asset α ∈ S_i; i.e., each asset α that node i is willing to send to another node. Given node i, additionally consider each neighbor j of i that contains α in R_j; i.e., each neighbor j that desires to receive α. (Formally, we refer to the set NR_i^α = {j ∈ N_i: α ∈ R_j}, which consists of those neighbors j of node i such that R_j contains α.) If node j is not already in the tree, i.e., if it has no predecessor (as indicated by PredS(j) = 0), then it can acceptably be added to the tree by adopting node i as its predecessor. For this, we set PredS(j) = i together with AssetS(j) = α, which records the fact that each chain in the tree that passes through this particular (i. j) link is accompanied by sending asset α from node i to node j.

If now j = i* (which can result because i* is not assigned a predecessor initially), we have discovered a chain beginning with node i* that results in a loop which qualifies as a mutually beneficial exchange cycle (where each participant receives a desired asset and in return sends a willingly exchanged asset). The Breakthrough Routine handles this outcome by identifying the cycle and updating the flows and the structure of G* appropriately.

Following the updates of the Breakthrough Routine, the scanning routine is reinitiated within the Main Routine by selecting a new i* from N^o (where i* may be the same as before if it is not removed from N^o during breakthrough).

Alternatively, the scan from a given node i* may terminate with ScanSet empty and without achieving breakthrough. In this case, i* is removed from N^o and once more the scanning routine is reinitiated within the Main Routine to select a new i* from N^o.

We let N_i^o = N_i ∩ N^o denote the (current) neighbors of node i that are in N^o. Hence N_i^o, which starts the same as N_i, may shrink as nodes are removed from N^o. This also modifies the definition NR_i^α = {j ∈ N_i: α ∈ R_j} to become NR_i^α = {j ∈ N_i^o: α ∈ R_j}, identifying the neighbors of i in N^o that desire to receive asset α.

Termination of the Main Routine occurs when N^o contains only a single node (|N^o|= 1), since then this node has no other nodes it can exchange with.

The formal design of the algorithm is as follows.

The algorithm can be modified to save part of the tree after the completion of each forward scan, but the computational savings will not usually be enough to warrant the effort. Reverse scanning provides a more interesting modification and can be accomplished by interchanging R and S in each of the instructions of the Forward Scanning Routine. Forward scanning and reverse scanning can also be done together, switching from one to the other on selected iterations. In this case, breakthrough is recognized when j = PredS(i) on a forward scan yields PredR(j) > 0 (where PredR(j) was set on a reverse scan), or when j = PredR(i) on a reverse scan yields PredS(j) > 0 (where PredS(j) was set on a forward scan). To show how reverse scanning can be joined with forward scanning, Appendix 3 gives an example where a single iteration of reverse scanning is applied before launching the forward scanning algorithm.

The Breakthrough Routine that accompanies the Forward Scanning Routine may now be described as follows. The preceding observations and the example in Appendix 3 disclose how to modify this routine for reverse scanning or for combinations of forward and reverse scanning.

6 Advanced forms of combinatorial chaining for more complex AEP models

There are problems that are too complex to be given mathematical formulations that fully capture their subtleties and that are simultaneously capable of being solved by standard math programming algorithms. In adopting the perspective of Quantum Bridge Analytics, we embrace strategies for such problems that allow their objectives to be pursued approximately and flexibly, thus admitting approaches that solve variations of these problems to emphasize alternative problem components in an adaptive fashion. As we have emphasized, our basic combinatorial chaining procedure allows this to be done when joined with network optimization by giving advanced methods that yield access to more complex AEP variants.

We show how this can be achieved for two chief extensions of the preceding AEP formulation that encompass a broad range of applications. The associated versions of combinatorial chaining provide flexible approximation methods that can be embedded in metaheuristic algorithms and afford the possibility of being incorporated into hybrid classical/quantum systems. In common with the most effective algorithms for QUBO problems, a natural basis for these combinatorial chaining methods derives from adaptive memory strategies (Glover et al., 2020, 2021b; Samorani et al., 2019; Wang et al., 2012).

6.1 Prioritizing the assets exchanged

In some applications of the AEP, participants may wish to prioritize certain exchanges of assets over others, preferring more strongly to receive particular assets and being more willing to relinquish certain other assets. Priorities attached to these preferences may also differ among different participants. Upon assigning numerical values to capture these preferences (as by indicating a dollar amount that different individuals attach to the value of different exchanges, or by making recourse to an agreed-upon set of subjective weights), the combinatorial chaining algorithm can be extended by prioritizing the selection of the elements i* in N^o or the choice of elements i in ScanSet, in each instance selecting the highest priority element from those available.

Priorities can also be used by such an extension to improve the choices for participants whose exchanges were less favorable on previous executions of the algorithm, since an effort to achieve a best overall collection of exchanges (such as a maximum number of beneficial exchanges) can result in better outcomes for some participants than for others. This means of exploiting the freedom to choose different elements in executing the basic steps of combinatorial chaining yields an approximation method for a problem whose subtleties render it unsuitable for a classical mathematical formulation, while allowing the flexibility to be adapted to different types of priorities. Such priorities can be introduced in the network formulation and embodied in probabilities for selecting moves in metaheuristic adaptations as in probabilistic tabu search (Glover and Laguna, 1997; Guemri et al., 2019; Xu et al., 1997). Combinatorial chaining provides the underlying structure for guiding the search to produce feasible solutions.

Priorities can also be employed to create larger breakthroughs earlier in the process of generating combinatorial chains, as by giving higher priority to participants with larger capacities (upper bounds) on the flows they can receive. The priorities can be based on measures applied to each base node (participant), such as total sums of capacities or means of capacities adjusted by standard deviations, and so forth. Refinements arise by considering the priorities of neighbors. For example, a new priority can be created for a node that is a weighted combination of its current priority and the priorities of neighbor nodes, where weights for neighbors are less than for the node under consideration. Such a process may also be repeated, using the new priorities as a basis for constructing another round of new priorities. (Additional repetitions may be expected to yield progressively less advantage.)

Particular applications give their own criteria for determining priorities. In exchanges of cryptocurrencies, for example, larger investors face the most negative impact by failing to make exchanges of a size deemed satisfactory, so assigning higher priorities to exchanges of such investors will usually result in the highest increase in utility. Using such priorities, choosing a node i* from N^o with the highest priority to become the root of the current directed tree, followed by choosing highest priority nodes i from ScanSet to continue building the tree, provides a compelling and easily implemented strategy.

As previously observed, there may also be situations where it can be relevant to place lower bounds as well as upper bounds on the number of units of different assets exchanged by different participants. In a cryptocurrency application, for example, an investor may only be interested in transactions that result in receiving a specified number of units of a given asset. To illustrate, an investor represented by a node i may seek an exchange in which i receives precisely 100 units of Ethereum (ETH), represented by asset α (∈ R_i) (accompanied, for example, by i sending units of Bitcoin (BTC) or Lumen (XLM) to other nodes). The AEP network model then captures this by putting a lower bound of 100 and an upper bound of 100 on the ETH arc (α, i[R]) → i[R]), giving L_i^α:R = U_i^α:R = 100. The situation where an investor may have an exact demand for an asset (modeled by setting the lower bound equal to the upper bound), and where this demand cannot be satisfied by an exchange involving any single other investor, is sometimes called splitting, i.e., the demand must be split into different transactions with different investors. Combinatorial chaining automatically handles splitting situations as well as other much more general situations. A simple illustration is where investor i will only consider an exchange that brings in at least L_i^α:R = 50 units of ETH, but would prefer to receive more units, up to a limit of U_i^α:R = 100. Any number of other investors, some who may not be neighbors of i, may be involved in transactions identified by combinatorial chaining.

In cases like these where the AEP model includes lower bounds on numbers of units received, exchanges can be prioritized in two phases, where Phase 1 is devoted to satisfying as many of the lower bounds as possible, and Phase 2 then sends additional flow through the network subject to satisfying upper bounds. These two phases are not required to have the same priorities for selecting nodes on exchange cycles.

Machine learning provides a natural way to facilitate priority generation. A strategy of varying the priorities may yield better overall outcomes for a particular objective, for example, and machine learning can be used to help identify a strategy that leads to the most desirable results. An instance of machine learning called Programming by Optimization (Hoos, 2012) is often effective for choosing parameters for optimization algorithms and may be useful in determining priorities in the combinatorial chaining context. Learning can also be employed as clustering-based metaheuristics (Samorani et al., 2019). The flexibility of the AEP model additionally makes it relevant for applications in public health and pandemic containment, as discussed in Appendix 4.

6.2 Generalized networks

An important extension of the AEP arises where a unit of one asset may be exchanged for more or less than one unit of another asset. Networks in which the number of units received at the destination node (to-node) of an arc may differ from the number of units sent from the origin node (from-node) of an arc are called generalized networks (Glover et al., 1990, 1992) and the factor that determines the difference between the units sent and received is called the arc multiplier. For example, an arc multiplier of 1.5 implies that the to-node receives 1.5 units for every unit sent from the from-node. A variety of situations exist where assets may be exchanged other than on a one-to-one basis.

A convenient feature of the basic combinatorial chaining algorithm is that such multiplier effects can be captured by joining the treatment of priorities with a modification of the Breakthrough Routine. The amount of flow transmitted across a chain of generalized arcs on a path leading from the root node i* to a subsequent node i equals the product of the multipliers on the arcs between i* and i. Thus, for example, if the chain consists of the succession of arcs (i*, i1), (i1,i2), (i2,i3), with i3 = i, and if the multipliers on these three arcs are 0.6, 2.0 and 1.2, then a unit of flow sent from node i* becomes 0.6 × 2.0 × 1.2 = 1.44 units of flow received at node i3. The Breakthrough Routine can be readily modified to incorporate this effect, using it to identify the limits on flows required to compute updated flows across the entire cycle and to determine which assets or elements must be removed from their associated sets due to these updates.

The approaches of introducing exchange priorities and capitalizing on the ability to incorporate arc multipliers in association with generalized networks can be combined to cover an additionally expanded range of practical problems, which may be usefully exploited by metaheuristic algorithms in the QBA context.

7 Concluding remarks

The relevance of Quantum Bridge Analytics for real world applications has been demonstrated by showing an important instance where we are able to apply the QBA perspective to the challenging AEP, which opens up numerous applications in financial investment, resource allocation, economic distribution and collaborative decision making. The linkage of network optimization with metaheuristic optimization via combinatorial chaining gives rise to an Asset Exchange Technology that can address and solve a wide range of practical variations.

Present day quantum computers can only handle small AEP problems, due to the limited number of qubits they encompass, but the integration of network formulations and combinatorial chaining is capable of accommodating AEP problems of significantly greater dimension. Through these connections, the AEP model gives an important class of optimization problems that can be usefully approached within the QBA domain, providing a foundation for further advances in the future as quantum computing technology becomes more mature.

Appendices

Appendix 1: Blockchains and decentralized market making

Decentralized market making is an intriguing concept that would require a detailed exploration, as it will likely emerge as critical factor for enabling scalable liquidity. But there are many questions to be answered. For example, what is the value of contributions by the decentralized market makers? Also, could these small investments held by the market—provided to equalize values in an exchange—be aggregated into baskets, and could those baskets be traded? How do we accurately assess the risks of items in baskets, to flow them up to the basket, to avoid “toxic assets” being included?

Finally, it should be noted that a computational system or agent that learns what a user wants to buy or sell, or might be willing to trade, would be quite valuable as an e-commerce tool because it provides a means to unveil the deeper purchase intentions of users. AI based agents could assist not only in the process of helping the user to determine what they might be willing to trade for or buy but could even help the user discover new purchase intentions that might lead to greater personal satisfaction. In other words, instead of just contributing to the accumulation of more useless stuff in their lives, such a system could explore more complex human values, as opposed to those reflecting desires and whims stimulated by media and advertising.

For example, if an AI held a model that understood the OCEAN Big Five personality traits, which was used so effectively by Cambridge Analytica in 2016, it could predict that the user has a high degree in a single trait, openness to new experiences. By balancing knowledge around both investment planning and personality traits, the advisor could provide more balanced advice to the user that would lead to greater personal satisfaction and fulfillment. A strictly financial based AI advisor would simply recommend one asset class over other, or the diversification into additional classes. But an AI advisor that used both financial optimization as well as heuristics about human personality and psyche, understanding the complex needs of the investor, might suggest to keep 95% of the portfolio within financial instruments, but propose that 5% could be invested in experiential learning for the user, in other words, investing in him or herself. This could include travel to learn a new language or a workshop to learn a new skill, possibly with permission to tap into the user’s online “bucket list”—the list of things you'd like to do before you “kick the bucket.”

To put this into the context of the AEP problem and combinatorial chaining, consider a situation with User A who has inherited a somewhat odd abstract painting from a distant relative in France, that doesn't have much value on the resale market in America. However, on a combinatorial exchange market, there may be a chance of trading it for something not only less objectionable but desirable for all parties. Her asking price is a value of $3000. Now, because her interaction with the exchange is managed by a user agent with access to her private “bucket list,” the trusted agent can now look for something that matches items on his list. It turns out that she has always wanted to take a class at the Cordon Bleu cooking school and to learn some French. So our agent can scan against other agents and listings, to find User B who wants to trade a $3000 workshop pass at Cordon Bleu for ten day stay in a beachfront Airbnb on some nice tropical island. The combinatorial chain holds that in place while finding a third or fourth transaction to make the combinatorial exchange pareto-optimal for all users. Fortunately, it finds User C who has a modest bungalow on a beach in the Marquesas, which doesn't get much Airbnb interest because it is too remote. However, that person looks at the painting, and realizes it was painted by the singer Jacques Brel, who was a great singer but lousy painter, and actually has quite a bit of value in the Marquesas because Jacques Brel spent his last days on the island of Hiva Oa, following the footsteps of Paul Gauguin and learning how to paint untamed landscapes that were so bad they looked abstract. So his agent offers a 3 week stay for that painting!

In this way, an AI-based financial advisor would advise in a more human and humane way. Thus, metaheuristic optimization via asset exchange technology could be applied directly to the issues of happiness, life goals and meaning. For user A, the lifelong goal of learning how to master the art of French cooking. For User B, a desperately needed vacation he couldn't afford otherwise. And for User C, the lifelong goal of appearing on Antique Roadshow, to show off a barn find of a lifetime. We thus can ascend from cold process of optimizing utility functions to optimizing the human condition.

Appendix 2: Illustration of the network structure of NetAEP0

The structure of the network NetAEP0 created in Sect. 4 is illustrated in the following diagram, where the i nodes are represented in their duplicated form i[R] and i[S], giving rise to the arc i[R] → i[S], for a network with N = {1, …, 6}. The assets α are represented by the letters A, B, C, D and E, giving rise to asset nodes of the form (α, i[S]) and (α, j[R]) which are joined by arcs (α, i[S]) → (α, j[R]) (called α-linking arcs in Sect. 4), where i and j may vary but the asset α (= A, B, …, etc.) must be the same in each such arc. It should be noted that these linking arcs do not have limiting bounds on their flows other than an implicit lower bound of 0.

The arcs of the network can be represented by a succession of columns of R-labeled nodes and S-labeled nodes, in a pattern that begins with the R-labeled i nodes i[R], followed by the S-labeled i nodes i[S], followed in turn by the S-labeled asset nodes (α, i[S]), then followed by the R-labeled asset nodes (α, j[R]) and finally followed by the R-labeled i nodes i[R] to repeat the pattern. A further interesting pattern seen in the diagram is that all S-labeled nodes have exactly 1 arc entering but may have multiple arcs leaving, while all R-labeled nodes have exactly 1 arc leaving but may have multiple arcs entering. The i nodes are enclosed in circles in the diagram and the asset nodes are enclosed in rectangles.

Since the asset arcs (linking arcs) do not have bounds on their flows, the foregoing pattern implies that an asset arc whose S-labeled node has a single arc out can be collapsed to be represented only by the R-labeled node, and an asset arc whose R-labeled node has a single arc in can be collapsed to be represented only by the S-labeled node. It should be emphasized that the staged structure shown in the diagram above is slightly misleading, since cycles typically vary in length and, in addition, duplicated i nodes may be encountered at various stages without implying they form a cycle that can be traced back to a previous instance of a duplicated node. The i indexes and the assets in the diagram have been ordered to show the patterns produced by arranging the nodes in columns. By contrast, the algorithm given in Sect. 4 for generating the network applies for any ordering of the indexes i in N and is independent of any ordering of the assets, which shows that such orderings are irrelevant in the general case.

Appendix 3: Illustration for reverse scanning

Appendix 4: Additional applications of the Asset Exchange Problem in public health and pandemic containment

The AEP arises in a variety of contexts, and recently, a new class of problems has become quite pertinent: the application of optimization processes to nonpharmaceutical interventions used in public health and pandemic containment. The basis of our approach on a form of cooperative optimization, where multiple parties with complex criteria collaborate as well as compete for resources, becomes additionally relevant in such situations where the objective to be optimized can be expressed in terms of the number of lives saved.

This is an area that is still in its infancy, and we make general observations about its nature and importance that should be considered speculative at the current stage. In the form of cooperative group optimization treated here, our approach generalizes processes that seek exchanges of pandemic resources or classes of citizens to enable combinatorial optimization. For example, a simple instance of such a system would be in the setting of elementary schools, in the formation of classroom bubbles to limit community spread of a highly infectious virus. In this example, a school wishes to allocate students and teachers to classroom bubbles to control the spread of the virus that currently poses a threat to health.

At present, schools assign students to bubbles in an ad hoc fashion. It becomes important to consider how this can be improved if additional information were available to assess the risk of infection for individual students, or infection via their home bubbles due to family members in high-risk occupations or the incidence of vaccination. We then pose the question: how would the formation of bubbles be modified to reduce the overall risk for the community? Each bubble is like a portfolio, and the assets in those portfolios contain their own risk levels. Key considerations are summarized by posing the further questions: Is it preferable to assign low risk students to low-risk bubbles, or to spread the risk around? If the school intended to achieve a kind of incremental herd immunity, then it might be supposed that it would be better to assign a low number of higher risk students from anti-vax families, with a larger number of low-risk students that belong to highly vaccinated families. However, when the wishes of individual vaccinated parents enter into the equation, these parents may not wish to allow their children to mix with children from unvaccinated households. Is there some science that could help to settle this issue?

The AEP framework makes it possible to address such issues using combinatorial swaps—moving interchangeable students around between bubbles, to seek more optimal configurations. Again, by enabling all potential complex exchanges, splits and aggregations to compose bubbles optimally, the school could decrease its overall risk of community spread. However, the computational complexity of this type of complex combinatorial exchange trading produces an NP-hard problem. This is further complicated by the inclusion of constraints—whether some students have special needs, certain students tend to be disruptive, and so forth—which increase the complexity of the problem.

The foregoing example is only one of many other possible areas that can be explored with both QUBO and AEP approaches, ranging from the allocation of scarce testing kits, to the early detection of asymptomatic spreaders, to the implementation of anomaly detection applications for improving the odds of early detection of variants of interest and concern. However, the most interesting is the vaccine allocation problem.

In the midst of a pandemic such as the one we are facing today, public health officials must make rapid vaccine allocation decisions—choosing who will receive the vaccines, where and when. Currently, there are two approaches to distributing vaccines to the general population: pull-based (in which requests from healthcare providers for specific quantities are filled) and push-based allocation (which is focused on distributing quantities to achieve equity among priority groups). The current preferred solution is to distribute the majority of vaccine doses via pull-based requests, while a smaller percentage of vaccine doses are held back by public health officials who must make decisions on how to allocate these doses to address and correct the inequities that may arise in a strictly pull-based process.

These decisions are extremely complex, and intersect with both logistical and ethical perspectives, especially when dealing with priority groups such as healthcare personnel, the elderly and people with certain health risks. The solutions must be fair, simple, effective (such as getting the right type of vaccines to specific locations), cognizant of cold chain constraints and quantity management. It is simply not possible for humans to make optimal decisions in this case. This is an ideal problem for mathematical optimization, that could help humans in making more optimal decisions.

Researchers have already begun using mixed integer programming to address this problem. This tool has proven to be valuable in deciding what percentage of available vaccines to keep in reserve for push-based allocation. As demonstrated in studies reported in Part 1 of this tutorial (Glover et al., 2021a, 2022), the use of algorithms specifically designed for QUBO and QUBOPlus models yield better solutions than MIP algorithms for these problem classes when the MIP algorithms are allowed to run one to three orders of magnitude longer. Moreover, the best algorithms for QUBO-related applications can obtain high quality solutions to problems much larger than the MIP approaches are capable of handling. In the QUBO-Plus category, the AEP model and its specialized algorithm afford a way to enlarge the strategies available for identifying a more efficient and equitable way to distribute vaccines, considering the factors highlighted here. Furthermore, with the significant risk for wastage of ultracold doses, faster optimization technologies could be valuable for optimizing real-time local distribution situations.

Finally, it may be possible to use these QUBO-related optimization technologies in the realm of behavioral economics to address situations where people often do not act in their own best interest. Hundreds of behavioral biases affect our daily decision-making. Many of those biases are accentuated in situations of stress, fatigue, propaganda, or fear. During a pandemic, both during lockdown and as vaccines have been released, factors like optimism bias and vaccine hesitancy impact the calculations people make on the probability of getting sick and dying. Compounding this situation, the lifting of social distancing measures can produce a false sense of security that worsens some of these biases and causes people to take fewer precautions. Through the relevance of the AEP model and its solution approach for cryptocurrency applications, it may be possible to use the AEP technology, in concert with cryptocurrency-based behavioral incentive tokens or nudge-based interventions, to address these challenges in behavioral economics as well. [See: https://www.zs.com/insights/how-behavioral-science-can-solve-vaccine-hesitancy and https://mgmt.wharton.upenn.edu/wp-content/uploads/2021/03/Covid19_Vaccine-Uptake-Behavioral-Science_Task-Force_Report_Feb-23-2021.pdf].

In sum, in the fight against a virus such as COVID-19, using technology that enjoys two orders of magnitude faster optimization for significantly larger variable spaces would allow for faster and better predictions about the spread of the virus, the ability to cluster higher risk cases more quickly and accurately for scarce testing supplies, and perhaps also, demonstrate that AI can be ethical.