betaFeedback

WorksComputer Science

A symbolic approach to discrete structural optimization using quantum annealing

Abstract

With the advent of novel quantum computing technologies, and the knowledge that such technology might be used to fundamentally change computing applications, a prime opportunity has presented itself to investigate the practical application quantum computing. The goal of this research is to consider one of the most basic forms of mechanical structure, namely a 2D system of truss elements, and find a method by which such a structure can be optimized using quantum annealing. The optimization will entail a discrete truss sizing problem - to select the best size for each truss member so as to minimize a stress-based objective function. To make this problem compatible with quantum annealing devices, it will be written in a QUBO format. This work is focused on exploring the feasibility of making this translation, and investigating the practicality of using a quantum annealer for structural optimization problems. Using the methods described, it is found that it is possible to translate this traditional engineering problem to a QUBO form and have it solved by a quantum annealer. However, scaling the method to larger truss systems faces some challenges that would require further research to address.

Introduction

Quantum computers are rather unique devices that, by leveraging quantum mechanical principles, theoretically allow certain types of problems to be solved much more efficiently than is possible with classical computers [1]. While classical computers use binary bits, 1s and 0s, to perform their computations, quantum computers make use of quantum bits. Quantum bits, or qubits, can not only represent the classical 0 and 1 states, but can also exist in a quantum superposition of these states. This quantum superposition, when leveraged effectively, is one of the reasons why quantum computers promise better performance in certain applications.

There are two main types of quantum computers currently in development, being the General Purpose Quantum Computer (GPQC) and the Quantum Annealer (QA). With the GPQC, most of the potential improvements stem from the fact that these systems can run complex quantum algorithms, allowing for more efficient problem-solving methods to be devised. An overview of quantum algorithms is given by Montanaro [2]. On the other hand, a QA can only use the quantum annealing algorithm to solve very specific types of optimization problems, known as quadratic unconstrained binary optimization (QUBO) or Ising model problems [3]. The QA is said to leverage quantum tunneling to aid in finding optimal solutions to optimization problems [4].

Both quantum computing technologies are still quite novel, and quantum computing hardware is still in its infancy compared to the advanced state of classical computing technologies. Research into practical applications of quantum computing stem only from the last several years, however, some studies have already shown promising results [5, 6, 7, 8, 9, 10, 11, 12]. A review of applications on structural mechanics is given by Tosti Balducci et al. [13]. Furthermore, in industry, some companies are already pushing for the development of early practical applications of quantum computing [14, 15]. For example, Airbus has posted the Airbus Quantum Computing Challenge. One of the challenges is to optimize a wingbox structure, the main load-bearing component in aircraft wings, using a quantum computer [16]. Another example comes from Volkswagen, who have researched how a QA can be used to optimize a traffic flow problem [6]. Volkswagen has already applied this research for the real-time optimization of public transport routes in Lisbon [17].

In the aerospace industry there is a continuous demand to develop the most lightweight structures, as this can lead to increased fuel efficiency, or increased payload capacity, both of which can lead to higher profits. This research will investigate the concept of using a quantum computer to assist in the optimization of mechanical structures. More specifically, the optimization of 2D truss structures will be targeted, as they are among the simplest structures to start with and are easily scalable to arbitrarily complex forms. Of the two types of quantum computers, the QA is chosen due to the higher level of technological maturity compared to GPQC, offering significantly more qubits of processing power. The main commercial supplier of QA technology is the company D-Wave Systems Inc. In this research, the D-Wave 2000Q quantum annealer, which has roughly 2000 qubits available, is used. During the execution of this research, a monthly allowance of 60 seconds of quantum processing unit (QPU) access time was available. This limit was taken into account for the scope of the testing that was performed. Because the QA can only solve specific types of optimization problems, the objective in this work will be to investigate how the truss optimization problem can be made compatible with the QA.

The rest of the paper will start with a brief description of the background on QA in § 2.

Background on QA: QUBO and Ising Formulations

For any problem that one wishes to solve using a QA, the first step is to ensure the problem is written with either a QUBO or an Ising formulation. In both cases, the QA attempts to find a solution for which the Hamiltonian energy is minimal.

To define a QUBO problem, an N×NN \times N matrix QQ is needed. The matrix QQ is typically written as an upper triangular matrix. The QA attempts to find the optimal binary bitstring xx of length NN that minimizes the Hamiltonian energy HH, as shown in eq. (1) [18]. When a solution to the QUBO problem is found, the binary variables in the solution vector xx will then have values of either 0 or 1.

min⁡(H)=xTQxs.t.xi∈{0,1} ∀i∈{1,2,…,N}(1)\begin{aligned} \min(H) &= \mathbf{x}^{T}Q\mathbf{x} \\ \text{s.t.}\quad&x_i \in\{0,1\}\ \forall i \in\{1,2,\ldots,N\} \tag*{(1)} \end{aligned}

In the Ising formulation, the system energy is given by a Hamiltonian function, as shown in eq. (2) [3, 19, 20, 21, 22, 23, 24, 25, 26].

H(s)=∑i=1Nhisi+∑i<jJijsisj(2)H(\mathbf{s}) = \sum_{i=1}^{N} h_i s_i + \sum_{i<j} J_{ij}s_i s_j \tag*{(2)}

In this equation, s=[s1,s2,…,sN]\mathbf{s} = [s_1,s_2,\ldots,s_N] are Ising spins, which can take values of either -1 or 1. The parameters hih_i and JijJ_{ij} are qubit biases (self-interaction) and coupling strengths (qubit-qubit interaction) respectively. The summation as defined in eq. (2) then yields the Ising Hamiltonian HH [3, 21]. The QA will attempt to find a solution for the Ising spins in s\mathbf{s} for which the Hamiltonian energy HH is minimal.

For this research, the QUBO problem framework is used, because the binary nature of the problem variables provides a convenient foundation to define a truss optimization problem. This will be described in the upcoming section.

Problem Description

To explore the feasibility of casting a structural optimization problem into a QUBO format, simple two-dimensional truss optimization problems will be investigated. A discrete truss sizing optimization problem can be defined, whereby the cross-sectional area of truss members can be chosen from a predefined discrete set (e.g., a finite number of cross-sectional configurations as provided by the truss supplier). The objective of the optimization is to find the cross-sectional area of each truss member such that the stress in every truss member is as close as possible to the material’s limit stress, thereby achieving the optimal use of material and hence minimum weight of the structure.

The truss systems that are defined for this research incrementally increase in their complexity. In total, three truss systems are defined: a basic two-truss system, a three-truss system, and a slightly more complex four-truss system. The three sample truss systems are shown in Figure 1 to Figure 3.

Figure 1. Two-truss system

Figure 3. Four-truss system

Figure 2. Three-truss system

The exact definitions of these truss systems, the boundary conditions, and the applied loads are given in Table 1. For each system, the same fictitious material is used, with a Young’s modulus of 200 GPa, and a material limit stress of 100 MPa. The material limit stress is assumed to be identical for both compressive and tensile loads. Furthermore, for every truss element, three different allowable choices for the truss cross-sectional area are defined, as shown in Table 2.

Two-TrussThree-TrussFour-Truss
NodesNodeX [mm]Y [mm]NodeX [mm]Y [mm]NodeX [mm]Y [mm]
N100N1-500500N10500
N21000-1000N2-500-500N20-500
N30-1000N3500100N35000
---N400N410000
ElementsElementStart NodeEnd NodeElementStart NodeEnd NodeElementStart NodeEnd Node
E1N1N2E1N1N4E1N1N3
E2N2N3E2N2N4E2N2N3
---E3N3N4E3N1N4
------E4N3N4
LoadNodeFxF_x [kN]FyF_y [kN]NodeFxF_x [kN]FyF_y [kN]NodeFxF_x [kN]FyF_y [kN]
N20-70N40-100N40-100
BCsNodedxd_x [mm]dyd_y [mm]Nodedxd_x [mm]dyd_y [mm]Nodedxd_x [mm]dyd_y [mm]
N100N100N100
N300N200N200
---N300---

Table 1. Nodal coordinate definitions, element connectivity, and load and boundary condition definitions. Fx/yF_{x/y} and dx/yd_{x/y} are the prescribed nodal forces and displacements along x/yx/y direction, respectively

Two-Truss Choices [mm2^2]Three-Truss Choices [mm2^2]Four-Truss Choices [mm2^2]
ElementsSmallMidLargeSmallMidLargeSmallMidLarge
E18009001000400500600240025002600
E214001500160095010501150240025002600
E3---700800900190020002100
E4------240025002600

Table 2. Definition of discrete choices of cross-sectional area for truss system elements.

Having defined the three sample problems, the next step is to start investigating the method by which these discrete truss sizing optimization problems can be cast into a QUBO format. In the upcoming section this process will be described, along with the difficulties and pitfalls that were encountered.

Method

General Concept

For a truss system consisting of NN truss elements, a set of CC discrete choices is defined for the truss cross sectional area for every truss element. As such, for every truss element nn the set of possible choices can be written as shown in eq. (3).

An,set={An,1,An,2,…,An,C}(3)A_{n,set} = \{A_{n,1}, A_{n,2}, \ldots, A_{n,C}\} \tag*{(3)}

To define the cross-sectional area of truss nn, a set of binary qubit variables is needed that each corresponds to one of the possible choices of cross-sectional area, giving eq. (4):

qn,set={qn,1,qn,2,…,qn,C}q_{n,set} = \{q_{n,1}, q_{n,2}, \ldots, q_{n,C}\}

With: qn,c∈{0,1} ∀ c∈{1,2,…C}q_{n,c} \in\{0,1\}\ \forall\ c \in\{1,2,\ldots C\}

{#eq:4}

The total cross-sectional area of truss nn can then be defined by summation of the discrete choices and their corresponding binary qubit variable as shown in eq. (4).

An=∑c=1Cqn,cAn,c(4)A_n = \sum_{c=1}^{C} q_{n,c}A_{n,c} \tag*{(4)}

In the case that, for truss nn, only one of the qubits in qn,setq_{n,set} is equal to 1, and the others are equal to 0, then this binary variable would correspond directly to a particular choice in cross-sectional area. For a truss system of NN truss elements and CC discrete choices per truss element, the number of variables needed would become N×CN \times C in total. Together, they form the solution vector of the problem. For example, for the two-truss problem, the solution vector would be defined as:

q=[q1,1, q1,2, q1,3, q2,1, q2,2, q2,3](5)\mathbf{q} = [q_{1,1},\ q_{1,2},\ q_{1,3},\ q_{2,1},\ q_{2,2},\ q_{2,3}] \tag*{(5)}

To select the mid-sized choice for each truss element in the two-truss problem, the solution vector would evaluate to:

q=[0, 1, 0, 0, 1, 0](6)\mathbf{q} = [0,\,1,\,0,\,0,\,1,\,0] \tag*{(6)}

It may be noted at this point that it is technically possible to select multiple cross-sectional areas for a single truss element. This would occur when a truss element has more than one associated binary variable set to a value of 1. Per eq. (4), this would mean that the area of the truss element becomes the summation of multiple available choices. However, in this research the goal is to make a single distinct choice from the available set of choices. Solutions where exactly one cross-sectional area is selected per truss element will be considered valid solutions. Any other potential solution, selecting either none, or multiple cross-sectional areas per truss element will be considered invalid.

With the truss cross-sectional area defined in terms of qubit variables as shown above, a symbolic solution process for the truss optimization problems has been conceived, such that the objective function would eventually be expressed as a QUBO function of these qubit variables. We would then use QA to find the solutions of these qubit variables which would minimize the objective function. The following steps summarize this symbolic solution process:

  1. Using the expression for the truss cross-sectional area, the element stiffness matrices of the truss members can also be written in terms of the qubit variables.

  2. Using the FEM assembly procedure, the symbolic global stiffness matrix of the entire truss structure can be assembled from each of the element stiffness matrices.

  3. Proceeding as normal with the FEM analysis, boundary conditions must be taken into account, and a vector of applied loads must be known. By inverting the symbolic global stiffness matrix, and multiplying this inverse matrix with the load vector, a symbolic vector of nodal displacements can be obtained.

  4. Using the symbolic vector of nodal displacements, and the known initial length of every truss element, symbolic expressions for the strains of truss elements can be set up.

  5. By multiplying the symbolic expressions of the truss strains with the Young’s modulus, symbolic expressions for the truss stresses are obtained.

  6. The symbolic expressions for the truss stresses will be used to construct an objective function for which the minimum solution encodes the optimal choice of cross-sectional area for every truss element in the structure.

  7. The symbolic objective function will be transformed into a QUBO format, then sent to D-Wave to find the minimum solution.

Symbolic Finite Element Method

Finding Expressions for Nodal Displacement

In the displacement-based linear finite element method for truss structures, the nodal Degrees of Freedom (DoFs) are the displacements. The stiffness matrix of each truss element can be defined by its nodal coordinates, cross-sectional area, and the Young’s modulus of the material. These element stiffness matrices are then assembled according to the element’s connectivity matrix to form a global system equation, typically as shown in eq. (7).

Ku=f(7)\mathbf{K}\mathbf{u} = \mathbf{f} \tag*{(7)}

The matrix K is known, and represents the global stiffness matrix of the finite-element structure. The vector f is also known, as this vector defines the forces which are applied to the structure. The goal for the linear finite-element problem is to find the solution vector u, which contains the displacement of every node in the structure. By knowing the displacements of all nodes in the structure, other metrics such as the element strain and stress can also be calculated.

As the element stiffness matrix depends on the cross-sectional area, which is now represented symbolically in eq. (4), the stiffness matrix of truss element nn will then be a function of the associated qubit variables in eq. (4). The assembled global stiffness matrix will then be a function of all the qubit variables of this structure, i.e., KK will be a function of the vector q\mathbf{q} as shown in eq. (5) for the two-truss example. A script has been written that can set up the truss finite-element system equation symbolically:

K(q)u=f(8)\mathbf{K}(\mathbf{q})\mathbf{u}=\mathbf{f} \tag*{(8)}

The above symbolic system equation has been implemented and solved in both Python and Matlab. Based on our experience, the Matlab backslash operator seems to solve for the solution u\mathbf{u} faster than Python Sympy. Hence, it is used here to obtain the symbolic nodal displacement vector:

u(q)=K(q)\f(9)\mathbf{u}(\mathbf{q})=\mathbf{K}(\mathbf{q})\backslash\mathbf{f} \tag*{(9)}

Having obtained the symbolic expressions for the nodal displacements, it became clear why this had been troublesome to calculate. The expressions for the nodal displacements are extremely long, even for such simple finite-element problems. This constitutes a bottleneck of the proposed approach, on which we will discuss later. Nevertheless, once we have obtained these expressions, the symbolic finite-element process can be continued.

Finding Expressions for Strain

Engineering strain is a common choice of strain measure for truss elements:

ϵ=Ldisp−L0L0(10)\epsilon=\frac{L_{\mathit{disp}}-L_0}{L_0} \tag*{(10)}

where the original length of the truss element is denoted as L0L_0, and the deformed length of the truss element as LdispL_{\mathit{disp}}. However, when this strain was implemented, it was found that this leads to a symbolic expression for the truss strain that contains many absolute functions. The appearance of these absolute functions was problematic as they prevented the symbolic expression from being written purely as a sum of quadratic polynomial terms, which is eventually necessary for the QUBO problem formulation.

To circumvent the appearance of the absolute functions in the symbolic expressions for the truss strain, the Green-Lagrange strain formulation was implemented, as given in eq. (11). Under the infinitesimal deformation assumption, when L0≈LdispL_0 \approx L_{\mathit{disp}}, eq. (10) and eq. (11) are equivalent.

ϵ=12(Ldisp2L02−1)(11)\epsilon=\frac{1}{2}\left(\frac{L_{\mathit{disp}}^2}{L_0^2}-1\right) \tag*{(11)}

With the Green-Lagrange strain implementation it was seen that the absolute functions no longer appeared in the symbolic truss strain expressions. Thus, the symbolic expressions for the strain of every truss element in the sample truss sizing optimization problems could be found. In turn, these can then be used to find expressions for the truss element stresses.

Expressions for Stress

Expressions for truss stresses follow from eq. (12), in which the material Young’s modulus is denoted by EE.

σ=Eϵ(12)\sigma=E\epsilon \tag*{(12)}

To give an example of the symbolic expressions for the truss element stresses, eqs. (13) to (15) give the stress in truss element 1 for the two-truss problem. Note, the expression for the stress in the truss element takes a fractional form.

σ1=N1D1(13)\sigma_1=\frac{N_1}{D_1} \tag*{(13)}

With:

N1=7.4046706×1029×q1,1+9.3715363×1029×q1,2+1.1569798×1030×q1,3+9.0707215×1030×q2,1+1.0412818×1031×q2,2+1.1847473×1031×q2,3+1.6660509×1030×q1,1×q1,2+1.8511677×1030×q1,1×q1,3+2.0825636×1030×q1,2×q1,3+1.4664165×1034×q1,1×q2,1+1.6833582×1034×q1,1×q2,2+1.6497186×1034×q1,2×q2,1+1.9152597×1034×q1,1×q2,3+1.893778×1034×q1,2×q2,2+1.8330206×1034×q1,3×q2,1+2.1546671×1034×q1,2×q2,3+2.1041978×1034×q1,3×q2,2+2.3940746×1034×q1,3×q2,3+1.943726×1031×q2,1×q2,2+2.0733078×1031×q2,1×q2,3+2.2214012×1031×q2,2×q2,3+3.1415357×1034×q1,1×q2,1×q2,2+3.3509714×1034×q1,1×q2,1×q2,3+3.5342277×1034×q1,2×q2,1×q2,2+3.5903265×1034×q1,1×q2,2×q2,3+3.7698428×1034×q1,2×q2,1×q2,3+3.9269196×1034×q1,3×q2,1×q2,2+4.0391173×1034×q1,2×q2,2×q2,3+4.1887143×1034×q1,3×q2,1×q2,3+4.4879081×1034×q1,3×q2,2×q2,3(14)\begin{aligned} N_1 ={}& 7.4046706 \times10^{29} \times q_{1,1} \\ &+ 9.3715363 \times10^{29} \times q_{1,2} \\ &+ 1.1569798 \times10^{30} \times q_{1,3} \\ &+ 9.0707215 \times10^{30} \times q_{2,1} \\ &+ 1.0412818 \times10^{31} \times q_{2,2} \\ &+ 1.1847473 \times10^{31} \times q_{2,3} \\ &+ 1.6660509 \times10^{30} \times q_{1,1} \times q_{1,2} \\ &+ 1.8511677 \times10^{30} \times q_{1,1} \times q_{1,3} \\ &+ 2.0825636 \times10^{30} \times q_{1,2} \times q_{1,3} \\ &+ 1.4664165 \times10^{34} \times q_{1,1} \times q_{2,1} \\ &+ 1.6833582 \times10^{34} \times q_{1,1} \times q_{2,2} \\ &+ 1.6497186 \times10^{34} \times q_{1,2} \times q_{2,1} \\ &+ 1.9152597 \times10^{34} \times q_{1,1} \times q_{2,3} \\ &+ 1.893778 \times10^{34} \times q_{1,2} \times q_{2,2} \\ &+ 1.8330206 \times10^{34} \times q_{1,3} \times q_{2,1} \\ &+ 2.1546671 \times10^{34} \times q_{1,2} \times q_{2,3} \\ &+ 2.1041978 \times10^{34} \times q_{1,3} \times q_{2,2} \\ &+ 2.3940746 \times10^{34} \times q_{1,3} \times q_{2,3} \\ &+ 1.943726 \times10^{31} \times q_{2,1} \times q_{2,2} \\ &+ 2.0733078 \times10^{31} \times q_{2,1} \times q_{2,3} \\ &+ 2.2214012 \times10^{31} \times q_{2,2} \times q_{2,3} \\ &+ 3.1415357 \times10^{34} \times q_{1,1} \times q_{2,1} \times q_{2,2} \\ &+ 3.3509714 \times10^{34} \times q_{1,1} \times q_{2,1} \times q_{2,3} \\ &+ 3.5342277 \times10^{34} \times q_{1,2} \times q_{2,1} \times q_{2,2} \\ &+ 3.5903265 \times10^{34} \times q_{1,1} \times q_{2,2} \times q_{2,3} \\ &+ 3.7698428 \times10^{34} \times q_{1,2} \times q_{2,1} \times q_{2,3} \\ &+ 3.9269196 \times10^{34} \times q_{1,3} \times q_{2,1} \times q_{2,2} \\ &+ 4.0391173 \times10^{34} \times q_{1,2} \times q_{2,2} \times q_{2,3} \\ &+ 4.1887143 \times10^{34} \times q_{1,3} \times q_{2,1} \times q_{2,3} \\ &+ 4.4879081 \times10^{34} \times q_{1,3} \times q_{2,2} \times q_{2,3} \tag*{(14)} \end{aligned}
D1=1.1847473×1032×q1,1×q2,1+1.3600415×1032×q1,1×q2,2+1.4994458×1032×q1,2×q2,1+1.547425×1032×q1,1×q2,3+1.7213026×1032×q1,2×q2,2+1.8511677×1032×q1,3×q2,1+1.9584598×1032×q1,2×q2,3+2.1250649×1032×q1,3×q2,2+2.4178516×1032×q1,3×q2,3+2.6656814×1032×q1,1×q1,2×q2,1+3.0600935×1032×q1,1×q1,2×q2,2+2.9618683×1032×q1,1×q1,3×q2,1+3.4817064×1032×q1,1×q1,2×q2,3+3.4001039×1032×q1,1×q1,3×q2,2+3.3321018×1032×q1,2×q1,3×q2,1+3.8685626×1032×q1,1×q1,3×q2,3+3.8251169×1032×q1,2×q1,3×q2,2+4.352133×1032×q1,2×q1,3×q2,3+2.5387442×1032×q1,1×q2,1×q2,2+2.7079938×1032×q1,1×q2,1×q2,3+3.2130982×1032×q1,2×q2,1×q2,2+2.901422×1032×q1,1×q2,2×q2,3+3.4273047×1032×q1,2×q2,1×q2,3+3.9667878×1032×q1,3×q2,1×q2,2+3.6721122×1032×q1,2×q2,2×q2,3+4.2312404×1032×q1,3×q2,1×q2,3+4.5334718×1032×q1,3×q2,2×q2,3+5.7121745×1032×q1,1×q1,2×q2,1×q2,2+6.0929861×1032×q1,1×q1,2×q2,1×q2,3+6.3468606×1032×q1,1×q1,3×q2,1×q2,2+6.5281994×1032×q1,1×q1,2×q2,2×q2,3+6.7699846×1032×q1,1×q1,3×q2,1×q2,3+7.1402181×1032×q1,2×q1,3×q2,1×q2,2+7.2535549×1032×q1,1×q1,3×q2,2×q2,3+7.6162327×1032×q1,2×q1,3×q2,1×q2,3+8.1602493×1032×q1,2×q1,3×q2,2×q2,3(15)\begin{aligned} D_1 ={}& 1.1847473 \times10^{32} \times q_{1,1} \times q_{2,1} \\ &+ 1.3600415 \times10^{32} \times q_{1,1} \times q_{2,2} \\ &+ 1.4994458 \times10^{32} \times q_{1,2} \times q_{2,1} \\ &+ 1.547425 \times10^{32} \times q_{1,1} \times q_{2,3} \\ &+ 1.7213026 \times10^{32} \times q_{1,2} \times q_{2,2} \\ &+ 1.8511677 \times10^{32} \times q_{1,3} \times q_{2,1} \\ &+ 1.9584598 \times10^{32} \times q_{1,2} \times q_{2,3} \\ &+ 2.1250649 \times10^{32} \times q_{1,3} \times q_{2,2} \\ &+ 2.4178516 \times10^{32} \times q_{1,3} \times q_{2,3} \\ &+ 2.6656814 \times10^{32} \times q_{1,1} \times q_{1,2} \times q_{2,1} \\ &+ 3.0600935 \times10^{32} \times q_{1,1} \times q_{1,2} \times q_{2,2} \\ &+ 2.9618683 \times10^{32} \times q_{1,1} \times q_{1,3} \times q_{2,1} \\ &+ 3.4817064 \times10^{32} \times q_{1,1} \times q_{1,2} \times q_{2,3} \\ &+ 3.4001039 \times10^{32} \times q_{1,1} \times q_{1,3} \times q_{2,2} \\ &+ 3.3321018 \times10^{32} \times q_{1,2} \times q_{1,3} \times q_{2,1} \\ &+ 3.8685626 \times10^{32} \times q_{1,1} \times q_{1,3} \times q_{2,3} \\ &+ 3.8251169 \times10^{32} \times q_{1,2} \times q_{1,3} \times q_{2,2} \\ &+ 4.352133 \times10^{32} \times q_{1,2} \times q_{1,3} \times q_{2,3} \\ &+ 2.5387442 \times10^{32} \times q_{1,1} \times q_{2,1} \times q_{2,2} \\ &+ 2.7079938 \times10^{32} \times q_{1,1} \times q_{2,1} \times q_{2,3} \\ &+ 3.2130982 \times10^{32} \times q_{1,2} \times q_{2,1} \times q_{2,2} \\ &+ 2.901422 \times10^{32} \times q_{1,1} \times q_{2,2} \times q_{2,3} \\ &+ 3.4273047 \times10^{32} \times q_{1,2} \times q_{2,1} \times q_{2,3} \\ &+ 3.9667878 \times10^{32} \times q_{1,3} \times q_{2,1} \times q_{2,2} \\ &+ 3.6721122 \times10^{32} \times q_{1,2} \times q_{2,2} \times q_{2,3} \\ &+ 4.2312404 \times10^{32} \times q_{1,3} \times q_{2,1} \times q_{2,3} \\ &+ 4.5334718 \times10^{32} \times q_{1,3} \times q_{2,2} \times q_{2,3} \\ &+ 5.7121745 \times10^{32} \times q_{1,1} \times q_{1,2} \times q_{2,1} \times q_{2,2} \\ &+ 6.0929861 \times10^{32} \times q_{1,1} \times q_{1,2} \times q_{2,1} \times q_{2,3} \\ &+ 6.3468606 \times10^{32} \times q_{1,1} \times q_{1,3} \times q_{2,1} \times q_{2,2} \\ &+ 6.5281994 \times10^{32} \times q_{1,1} \times q_{1,2} \times q_{2,2} \times q_{2,3} \\ &+ 6.7699846 \times10^{32} \times q_{1,1} \times q_{1,3} \times q_{2,1} \times q_{2,3} \\ &+ 7.1402181 \times10^{32} \times q_{1,2} \times q_{1,3} \times q_{2,1} \times q_{2,2} \\ &+ 7.2535549 \times10^{32} \times q_{1,1} \times q_{1,3} \times q_{2,2} \times q_{2,3} \\ &+ 7.6162327 \times10^{32} \times q_{1,2} \times q_{1,3} \times q_{2,1} \times q_{2,3} \\ &+ 8.1602493 \times10^{32} \times q_{1,2} \times q_{1,3} \times q_{2,2} \times q_{2,3} \tag*{(15)} \end{aligned}

For reference, the symbolic expressions for the truss stresses of each of the sample problems are available online [27].

Now that a method has been implemented that can write the stresses in terms of qubit variables, the next step is to set up an objective function that, when minimized, should yield the most optimal choice of cross-sectional area for every truss element in the structure. However, this process uncovered another challenge, which is discussed in the upcoming section.

Development of an Objective Function

Fractional Objective Function

Using the expression for the stress in a truss element, an objective function can be set up describing the difference between the truss element stress and the maximum limit stress allowed by the material properties. If such a difference is minimized, then the truss element will be as close as possible to the material failure stress, meaning the weight of the truss is implicitly minimized.

When setting up the objective function, it is important to consider that the truss element stress evaluates to a negative number for truss elements under compression. However, because it is not known beforehand which truss elements will experience compressive or tensile stresses, this poses an issue. It is not possible to apply an absolute function to the truss element stress, as such a mathematical function is incompatible with QUBO problem formulations. As an alternative, the expression for the truss element stress can be squared to ensure that it always evaluates to a positive number. To keep consistent units, this also means that the maximum allowable stress is squared. A minimization problem is obtained by squaring the difference between the squared material limit stress and the squared truss element stress. As such, for a single truss element nn, a minimization objective function can be defined as shown in eq. (16).

Fn=(σlimit2−σn2)2(16)F_n = \left(\sigma_{\mathit{limit}}^2-\sigma_n^2\right)^2 \tag*{(16)}

With eq. (16), the minimum solution should encode the choice of truss cross-sectional area that minimizes the absolute difference between the material limit stress and the truss stress. To set up an objective function that describes the entire system of truss elements, the summation is taken of the objective functions of every individual truss element, which leads to eq. (17).

F=∑n=1NFn=∑n=1N(σlimit2−σn2)2(17)F = \sum_{n=1}^{N} F_n = \sum_{n=1}^{N}\left(\sigma_{\mathit{limit}}^2-\sigma_n^2\right)^2 \tag*{(17)}

With eq. (17) a general method is obtained that can be used to set up an objective function for each of the sample problems. It is important to note that, because the truss element stresses σn\sigma_n are fractional in nature, as was shown in eqs. (13) to (15), the objective function from eq. (17) will also have a fractional form. Hence, the resulting objective function is referred to as the fractional objective function. To test whether this method of setting up an objective function works as expected, the objective functions are set up for each of three sample problems, and are evaluated by a brute-force analysis, i.e., the objective function is evaluated at every possible solution. The results for the three sample problems are shown in figs. 4 to 6, and were produced using the Matlab code which is available online [27]. The following global minimum solutions were found:

  • Two-truss problem: minimum at solution number 7, [0, 0, 1, 1, 0, 0]

  • Three-truss problem: minimum at solution number 21, [0, 0, 1, 1, 0, 0, 0, 0, 1]

  • Four-truss problem: minimum at solution number 7, [1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0]

The above brute-force results will be used as references to benchmark the performance of QA. One may be tempted to directly send the objective function in eq. (17) to QA and see how it performs. However, one challenging aspect remains: the function has a fractional form. Fractional objective functions are incompatible with QUBO problem formulations, and cannot be directly solved by the QA. As such, in the next section, a method is investigated by which a potential non-fractional objective function can be set up that approximates the original fractional one.

Non-Fractional Objective Function

In a QUBO-based objective function, only a summation of linear and quadratic terms is allowed. Therefore, in this section a potential method is investigated to formulate a non-fractional objective function for the discrete truss sizing optimization problem.

The reserve factor of a truss element gives a measure of how close the truss element is to material failure. The reserve factor for a truss element nn is calculated via eq. (18).

RFn=σlimit∣σn∣(18)RF_n = \frac{\sigma_{\mathit{limit}}}{\lvert\sigma_n\rvert} \tag*{(18)}
Fractional objective function for the two-truss problem

Figure 4. Fractional objective function for the two-truss problem. Global minimum is found to be solution number 7, corresponding to [0, 0, 1, 1, 0, 0].

Fractional objective function for the three-truss problem

Figure 5. Fractional objective function for the three-truss problem. Global minimum is found to be solution number 21, corresponding to [0, 0, 1, 1, 0, 0, 0, 0, 1].

Figure 6. Fractional objective function for the four-truss problem. Global minimum is found to be solution number 7, corresponding to [1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0].

To mitigate the absolute function for compatibility with QUBO, the material limit stress σlimit\sigma_{limit} and truss element stress σn\sigma_n can be squared. By doing so, a squared reserve factor can be calculated, according to eq. (19).

RFn2=σlimit2σn2(19)RF_n^2 = \frac{\sigma_{limit}^2}{\sigma_n^2} \tag*{(19)}

Using eq. (19) the theoretical optimal value of the squared reserve factor shall be 1 if the cross-sectional area can be varied arbitrarily. Given that the squared reserve factor is written as a fraction, this means that the numerator and the denominator should be equal to each other in the optimal case. In this case the numerator minus the denominator should also yield a result of zero. However, assuming that the currently known symbolic expression for the truss reserve factor actually describes a sub-optimal case, this will result in an error term. An optimization problem can then be set up for which the goal is to minimize this error, by simply squaring the expression. This ensures that the optimum solution will be the one where the squared error is closest to zero, giving an objective function for the minimization. The steps to this process are shown in eq. (20).

If:RFn2=σlimit2σn2andσn2=σN,n2σD,n2Rewriting:RFn2=σlimit2σD,n2σN,n2=NnDnWhen:RFn2=NnDn=1Then:Nn=DnOptimally:Nn−Dn=0Sub-optimally:Nn−Dn=ϵOptimizing:min⁡(ϵ2)⇒min⁡((Nn−Dn)2)(20)\begin{aligned} \text{If:}\quad RF_n^2 &= \frac{\sigma_{limit}^2}{\sigma_n^2} &&\text{and}\quad\sigma_n^2 = \frac{\sigma_{N,n}^2}{\sigma_{D,n}^2}\\ \text{Rewriting:}\quad RF_n^2 &= \frac{\sigma_{limit}^2\sigma_{D,n}^2}{\sigma_{N,n}^2} = \frac{N_n}{D_n}\\ \text{When:}\quad RF_n^2 &= \frac{N_n}{D_n}=1\\ \text{Then:}\quad N_n &= D_n\\ \text{Optimally:}\quad N_n-D_n &= 0\\ \text{Sub-optimally:}\quad N_n-D_n &= \epsilon\\ \text{Optimizing:}\quad\min\left(\epsilon^2\right) &\Rightarrow\min\left((N_n-D_n)^2\right) \tag*{(20)} \end{aligned}

Considering the above reasoning, the non-fractional objective function for a truss element nn is written in eq. (21).

Fn=(Nn−Dn)2=(σlimit2σD,n2−σN,n2)2(21)F_n = (N_n-D_n)^2 = \left(\sigma_{limit}^2\sigma_{D,n}^2-\sigma_{N,n}^2\right)^2 \tag*{(21)}

The objective function for the complete truss system is then found by taking the sum for all truss elements, as given in eq. (22).

F=∑n=1NFn=∑n=1N(σlimit2σD,n2−σN,n2)2(22)F = \sum_{n=1}^{N}F_n = \sum_{n=1}^{N}\left(\sigma_{limit}^2\sigma_{D,n}^2-\sigma_{N,n}^2\right)^2 \tag*{(22)}

This reformulated non-fractional objective function is again tested with the sample problems, using the brute-force analysis method [27], to find out if the minimum solutions remain the same as those of the original fractional objective function. The results of these analyses are shown in Figure 7 to Figure 9, with the global minimum solutions indicated with a small red circle. The following global optimum solutions were obtained:

Figure 7. Non-fractional objective function for the two-truss problem. Global minimum is found to be solution number 7, corresponding to [0, 0, 1, 1, 0, 0].

Non-fractional objective function for the four-truss problem

Figure 9. Non-fractional objective function for the four-truss problem. Global minimum is found to be solution number 1, corresponding to [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0].

  • Two-truss problem: minimum at solution number 7, [0, 0, 1, 1, 0, 0]

  • Three-truss problem: minimum at solution number 1, [1, 0, 0, 1, 0, 0, 1, 0, 0]

  • Four-truss problem: minimum at solution number 1, [1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]

Using the non-fractional objective function, the expected solution for the two-truss problem is returned. However, for the three- and four-truss problems, the results are however not those expected. Therefore this method is presumed to be flawed. In the method, the difference between NnN_n and DnD_n is considered, rather than considering the ratio Nn/DnN_n/D_n which defines the squared reserve factor. A solution that minimizes the difference

Non-fractional objective function for the three-truss problem

Figure 8. Non-fractional objective function for the three-truss problem. Global minimum is found to be solution number 1, corresponding to [1, 0, 0, 1, 0, 0, 1, 0, 0].

between NnN_n and DnD_n may not necessarily be the same solution for which the ratio between NnN_n and DnD_n is closest to a value of 1. Hence, this may be the source of the unexpected behavior produced by this objective function method. In the next section, an alternative method is discussed, with which a fractional objective function can still be made compatible with the QA.

Iterative non-fractional approximations to the fractional objective function

Ajagekar et al. developed a method with which the optimum solution to fractional objective functions can be found, by iteratively solving an adaptive non-fractional function [28]. The iterative scheme described by the authors is presented in eq. (23).

With: F=N(q)D(q)0: Initialize variablesiter=0λ=0obj=∞δ=10−61: while ∣λ−obj∣>δ2:iter=iter+13:Fnf(q)=N(q)−λD(q)4:find q^ s.t. min⁡(Fnf(q^))5:obj=λ6:λ=F(q^)(23)\begin{aligned} &\text{With: } F = \frac{N(\mathbf{q})}{D(\mathbf{q})}\\ &0:\ \text{Initialize variables}\\ &\mathit{iter}=0\\ &\lambda=0\\ &obj=\infty\\ &\delta=10^{-6}\\ &1:\ \mathbf{while}\ |\lambda-obj|>\delta\\ &2:\quad\mathit{iter}=\mathit{iter}+1\\ &3:\quad F_{nf}(\mathbf{q})=N(\mathbf{q})-\lambda D(\mathbf{q})\\ &4:\quad\text{find }\hat{\mathbf{q}}\ \text{s.t.}\ \min\left(F_{nf}(\hat{\mathbf{q}})\right)\\ &5:\quad obj=\lambda\\ &6:\quad\lambda=F(\hat{\mathbf{q}}) \tag*{(23)} \end{aligned}

In this scheme the fractional objective function F(q)F(\mathbf{q}), written in terms of the binary problem variables q\mathbf{q}, is rewritten into a non-fractional form. This happens in step 3 of the scheme, producing the non-fractional objective Fnf(q)F_{nf}(\mathbf{q}). If this non-fractional function can be written in a QUBO form, then the partially optimal solution q^\hat{\mathbf{q}} can be found using the QA, in step 4 of the iterative scheme. In step 6, the objective function value of the original fractional function is evaluated using the partially optimal solution that was found to the non-fractional function. When the difference between the objective function values found in consecutive iterations is less than δ\delta the while-loop is broken and the analysis has converged. Ultimately, the final solution that is found for q^\hat{\mathbf{q}} will be the minimum solution to the original fractional objective function.

This iterative method for finding the optimal solution to fractional objective functions was implemented in the Python scripts for the discrete truss sizing optimization problems [27]. However, the method was slightly extended, to include a user-defined maximum allowed number of iterations. This was added as an additional condition to while-loop in step 1 of eq. (23). In other words, defining step 1 as:

while ∣λ−obj∣>δ  AND  iter≤itermax(24)\mathbf{while}\ |\lambda-obj|>\delta\ \ \mathit{AND}\ \ \mathit{iter}\leq\mathit{iter}_{max} \tag*{(24)}

Setting a maximum number of iterations will help to prevent wasting excessive quantum computational time in the case that the analysis has difficulty converging on an optimal solution.

Objective Function Processing to Yield a QUBO Problem

With the iterative scheme that was defined by Ajagekar et al. in [28], the fractional objective function for the discrete truss sizing optimization problem can be solved by iteratively finding the solution to an adaptive non-fractional function. Once this non-fractional form is determined, there are a number of processing and simplification steps that can be taken to finally yield a QUBO problem. By reducing the complexity of the objective function, the QA might be able to more easily identify the global optimum solution. The processing steps will allow the user to fine-tune the performance of the QA more easily, and aid in finding valid solutions to the discrete truss sizing optimization problem. In the following sections the simplifications and processing steps are discussed.

High-Order Truncation

The first simplification to the rewritten non-fractional objective function is to truncate excessively high-order terms. Specifically, for a system with NN truss elements, any term in the objective function that is above NNth order can be truncated. These terms do not contribute any useful information about valid solutions to the optimization problem. Since, for a valid solution to the truss optimization problem, only NN number of qubits are expected to end in a 1 state, while all other qubits should end in a 0 state. Therefore, all terms in the objective function that are above NthN^{\mathrm{th}} order never contribute to valid solutions. These terms can therefore safely be truncated in order to simplify the overall objective function, while having no influence on valid problem solutions.

The objective functions generally contain every possible unique multiplication between the qubit variables. Therefore, truncating the excessively high-order terms from the objective function can have a very large impact on the overall complexity of the objective function. This was investigated with a simple Excel sheet, which is made available online [27]. For example, in the two-truss problem, a total of six qubit variables are used. In total, this gives 63 different unique multiplications of qubit variables from first to sixth order. For this problem, all terms above second order only contribute information to invalid problem solutions, as for valid solutions it is expected that exactly two qubit variables will be given a value of 1. As such, terms above second order can all safely be removed from the objective function. After truncating the terms above second order, only 21 total first- and second-order terms remain in the objective function. This means that the overall number of terms in the objective function is reduced by 66%. In a similar vein, for the three-truss problem, this truncation reduces the number of terms in the objective function by roughly 75%. For the four-truss problem, the reduction is approximately 80%. It is expected that such a significant reduction in the complexity of the objective function will benefit the QA, allowing it to more easily find valid global minimum solutions to the truss sizing optimization problems.

Linear Scaling

When submitting problems to the QA, there are a number of parameters that can be fine-tuned to alter or improve the performance of the QA. The magnitude of these parameters relative to each other is typically what drives the performance of the QA. To set a consistent baseline for solving the truss sizing optimization problems, it is therefore convenient to scale the magnitude of the problem to a user-defined value. In this way, the magnitude of the truss optimization problem can be scaled with respect to other constraints. Thus, a linear scaling of each of the terms in the objective function can be performed, to ensure that the terms have a consistent and controllable magnitude.

First, the term with the maximum absolute magnitude in the objective function, cmax⁡c_{\max}, must be found. Then, every term in the objective function FF can be divided by this magnitude, to perform the linear scaling. A user-defined parameter, cuserc_{\mathrm{user}}, is introduced to ensure that the maximum magnitude of the terms in the objective function can be exactly specified. Thus, the linear scaling of the objective function FF is performed as shown in eq. (25).

Fscaled=cuser×Fcmax⁡(25)F_{\mathrm{scaled}} = \frac{c_{\mathrm{user}} \times F}{c_{\max}} \tag*{(25)}

Inside the linearly scaled objective function FscaledF_{\mathrm{scaled}}, the term with the maximum magnitude will have a magnitude of cuserc_{\mathrm{user}}. By altering the value of cuserc_{\mathrm{user}}, the user is able to control the relative importance of the objective function with respect to other problem-specific parameters.

Non-Linear Scaling

Throughout the brute-force testing of the objective functions for the different sample problems in § 4.3, it was seen that with certain objective functions the global minimum solution and other local minimum solutions can have nearly identical function values. This was especially the case for the three-truss problem, using the fractional objective function. When the differences between solutions are small, it becomes difficult for the QA to find the global optimum solution. The main cause for very small differences between local minima and the global minimum is due to specific terms in the objective function with very small, high-precision coefficients.

Due to analog control errors, small and high-precision coefficients are difficult for the QA to correctly take into account [29]. Furthermore, when a problem is submitted to the D-Wave QA, it is by default automatically scaled (by auto_scale) to ensure the problem coefficients fall inside the controllable range of the QA. For linear QUBO coefficients this range is between -2 and 2. For the quadratic QUBO coefficients the maximum available range is between -2 and 1 [30], however, by default the QA used a range between -1 and 1. These ranges can be directly queried from the D-Wave solver by Python commands:

DWaveSampler().properties[’h_range’]

DWaveSampler().properties[’j_range’]

It is good to be mindful of this automatic scaling before submitting problems to the QA, to prevent cases where a problem is unexpectedly scaled down to a magnitude that cannot feasibly be controlled by the QA.

To assist the QA with small high-precision coefficients, it would be beneficial if these coefficients could be amplified. In turn, this may also amplify the differences between the global and other local minimum solutions. This would potentially help the QA in finding the global optimum solution. Furthermore, this may also help the QA to more effectively utilize information from the objective function, as previously insignificant terms may be amplified to a magnitude that the QA can actually take into account. To help address these issues, a non-linear scaling method was developed, with which very small coefficients in the objective function are scaled to become larger and more influential, while terms terms that are already significant are not scaled as much.

A Python function was created and implemented that performs this non-linear scaling. The method relies on simple user-defined parameters that will allow for manual tweaking once the problem has been fully implemented for use with the QA. Given the user-defined scaling parameter cNLc_{NL}, a positive coefficient cin+c_{in+} from the objective function is input into the non-linear scaling function. The non-linearly scaled coefficient cout+c_{out+} is then found by eq. (26).

cout+=cin+cin++cNL(26)c_{out+} = \frac{c_{in+}}{c_{in+} + c_{NL}} \tag*{(26)}

For negative input coefficients, cin−c_{in-}, the non-linear scaling is performed by eq. (27), yielding the negative non-linearly scaled coefficient cout−c_{out-}.

cout−=−cin−cin−−cNL(27)c_{out-} = -\frac{c_{in-}}{c_{in-} - c_{NL}} \tag*{(27)}

To determine if the input coefficient must be scaled using either eq. (26) or eq. (27), a simple if-statement is used. By setting cNLc_{NL} to be a certain small number, such as 0.025, the amount of scaling that is applied to small coefficients is much more aggressive than for relatively larger coefficients.

As a demonstration of the non-linear scaling, several plots are given in Figure 10, showing the influence of changing the parameter cNLc_{NL}. It can be seen that for small coefficients the scaling is much more significant than for relatively larger coefficients. However, for very aggressive values of cNLc_{NL}, such as 0.001, this can also cause all relatively large coefficients to become essentially equal. The use of this non-linear scaling function will therefore be a balancing act of increasing the importance of small coefficients, while not losing distinction for the larger terms. The Python code for the non-linear scaling function, and for producing the plot from Figure 10 is available online [27].

Figure 10. Non-linear scaling function for input coefficients between -1 and 1. The output of the function is shown for various values of the non-linear scaling parameter cNLc_{NL}.

The effect of the non-linear scaling is also investigated for the specific truss sizing sample problems. The non-linear scaling is performed during the iterative solving procedure. Specifically, it is performed between steps 3 and 4 of the procedure outlined in eq. (23), and is applied to the rewritten non-fractional objective function. The effect of the non-linear scaling is investigated for the first iteration of the sample problems. This first iteration is convenient to investigate, as eq. (23) shows that λ=0\lambda= 0, meaning that the objective function in step 3 in eq. (23) only involves the numerator of the original fractional objective function.

The rewritten non-fractional function is first linearly scaled, choosing the user-defined maximum coefficient to be cuser=1c_{user} = 1. This brings the function values in the energy landscape to a more reasonable magnitude and allows for the non-linear scaling to work as intended. Then, the non-linear scaling can be applied, using a scaling parameter of cNL=0.1c_{NL} = 0.1. The plots in Figure 11 to Figure 13 show both the original (linearly scaled) and non-linearly scaled energy landscapes of the first iteration in the solving procedure for the sample truss problems. It can be seen that the small fluctuations in the energy landscape are amplified, which should make the problem easier to solve for the QA. As such, the non-linear scaling will be applied when submitting problems to the QA.

Figure 11. Effect of non-linear scaling in two-truss problem, for the first iteration of the iterative non-fractional solving method.

Figure 13. Effect of non-linear scaling in four-truss problem, for the first iteration of the iterative non-fractional solving method.

It is important to note that this non-linear scaling function was developed solely for the purpose of increasing the differences between the global and local minima in the energy landscapes, as a part of this study. It is not intended to be used as a general-purpose tool for problems with unknown energy landscapes. Since, when using overly aggressive scaling factors for cNLc_{NL}, this may cause the global minimum solution to change. However, this is not expected to be an issue for the truss sizing optimization problem. In step 6 of the iterative solving procedure in eq. (23), the interim solution q^\hat{\mathbf{q}} is evaluated with the original fractional objective function, meaning the iterative procedure should eventually converge on the global optimum of the original fractional objective function.

Truncation of Insignificant Terms

Once the linear and non-linear scaling has been performed it is possible to further simplify the objective function. After all scaling has been applied, certain terms in the objective function might still have a magnitude very close to zero. Such terms are difficult for the QA to take into account, as there is a finite precision with which qubit biases can be controlled within the physical hardware of the QA [29]. Since the magnitude of terms in the objective function might be smaller than the precision that the QA can control, such terms cannot reliably be taken into account. This is because the analogue control-error for

Figure 12. Effect of non-linear scaling in three-truss problem, for the first iteration of the iterative non-fractional solving method.

the qubit biases can be larger than the actual term in the objective function. Thus, terms that are too small in magnitude can simply be removed from the objective function, as trying to include them is akin to simply introducing noise into the function. A conservative truncation magnitude, beyond the precision that the QA can control, is to remove terms with magnitudes smaller than 10−810^{-8}. This reduces the complexity of the objective function, which may have a positive influence on the ability of the QA to find the global optimum solution to the truss sizing optimization problem.

Unary Constraint

The majority of all possible solutions to the truss optimization problems are invalid. Solutions are invalid when an incorrect number of cross-sectional areas are selected. In other words, when either zero or more than one cross-section is selected for a truss member, the solution is invalid. Solutions can only be valid when exactly one cross-sectional area is chosen for every truss member. To promote the selection of valid solutions, the unary constraint is implemented.

For every truss element nn in a truss system, with a total of CC possible choices of cross-sectional area, eq. (28) must be true for valid solutions to the truss sizing optimization problem.

∑c=1Cqn,c=1(28)\sum_{c=1}^{C} q_{n,c} = 1 \tag*{(28)}

Since only one of the qubits on which this constraint acts must take a value of 1, while the others must all equal 0, this constraint is sometimes referred to as the unary constraint. Further elaboration on the unary constraint is given in [31]. In the context of the truss optimization problem, it enforces that only one cross-section is chosen per truss element. However, in the form shown in eq. (28), the constraint cannot be applied in the QUBO problem framework. This is because the constraint is currently written as an equality constraint, which per definition is incompatible with quadratic unconstrained binary optimization problems. For the constraint to become compatible with QUBO problems it must be rewritten as a minimization problem. A common method is to rewrite the equality constraint as a penalty function, using a ‘squared-error’ approach [32, 33]. This approach is also used, for example, in the works by Van Vreumingen et al. and Neukart et al. [6, 7]. Thus, the constraint can be rewritten as a minimization problem as shown in eq. (29).

(∑c=1Cqn,c)−1=0((∑c=1Cqn,c)−1)2=0(29)\begin{aligned} \left(\sum_{c=1}^{C} q_{n,c}\right)-1 &= 0 \\ \left(\left(\sum_{c=1}^{C} q_{n,c}\right)-1\right)^2 &= 0 \tag*{(29)} \end{aligned}

Now, adding in a penalty scaling factor λ\lambda, the Hamiltonian energy penalty function for the unary constraint becomes:

HU=λ((∑c=1Cqn,c)−1)2(30)H_U = \lambda\left(\left(\sum_{c=1}^{C} q_{n,c}\right)-1\right)^2 \tag*{(30)}

For the truss sizing optimization problems, only three possible choices of cross-sectional area are available per truss element, meaning that C=3C = 3. Therefore, eq. (30) can be expanded and simplified, as shown in eq. (31).

HU=λ(qn,1+qn,2+qn,3−1)(qn,1+qn,2+qn,3−1)H_U=\lambda(q_{n,1}+q_{n,2}+q_{n,3}-1)(q_{n,1}+q_{n,2}+q_{n,3}-1)
HU=λ(qn,12+qn,1qn,2+qn,1qn,3−qn,1+qn,1qn,2+qn,22+qn,2qn,3−qn,2+qn,1qn,3+qn,2qn,3+qn,32−qn,3−qn,1−qn,2−qn,3+1)(31)\begin{aligned} H_U=\lambda(&q_{n,1}^{2}+q_{n,1}q_{n,2}+q_{n,1}q_{n,3}-q_{n,1}\\ &+q_{n,1}q_{n,2}+q_{n,2}^{2}+q_{n,2}q_{n,3}-q_{n,2}\\ &+q_{n,1}q_{n,3}+q_{n,2}q_{n,3}+q_{n,3}^{2}-q_{n,3}\\ &-q_{n,1}-q_{n,2}-q_{n,3}+1) \tag*{(31)} \end{aligned}

Knowing that qn,c∈{0,1}q_{n,c} \in\{0,1\}, which means that qn,c2=qn,cq_{n,c}^{2}=q_{n,c}, the expression can be further simplified:

HU=λ(2qn,1qn,2+2qn,2qn,3+2qn,1qn,3−qn,1−qn,2−qn,3+1)(32)H_U=\lambda(2q_{n,1}q_{n,2}+2q_{n,2}q_{n,3}+2q_{n,1}q_{n,3}-q_{n,1}-q_{n,2}-q_{n,3}+1) \tag*{(32)}

Lastly, the final constant term can be dropped, since it is independent of the qubit variables, and does not affect the minimization problem. Doing so makes the unary constraint penalty function compatible with the QUBO problem framework. Since, the penalty function can now be written as a pure summation of linear and quadratic terms, as shown in eq. (33).

HU=λ(2qn,1qn,2+2qn,1qn,3+2qn,2qn,3−qn,1−qn,2−qn,3)(33)H_U=\lambda(2q_{n,1}q_{n,2}+2q_{n,1}q_{n,3}+2q_{n,2}q_{n,3}-q_{n,1}-q_{n,2}-q_{n,3}) \tag*{(33)}

By adding the unary constraint, for each truss element, to the overall truss sizing objective function, the QA is more likely to find valid solutions. The strength of the unary constraint can be fine-tuned by altering the value of the user-defined parameter λ\lambda. By trail and error it has been found that a good starting value of λ\lambda is to be twice the magnitude of the maximum term in the objective function. However, if invalid solutions are consistently found, the strength of the constraint can be increased until noncompliance with the constraint stops.

Quadratization

Up until this point, the objective function has been manipulated, scaled, and truncated in order for it to become more compatible with the QUBO problem formulation. However, one key issue has yet to be solved: the function might still contain many terms that are greater than quadratic order. Therefore, it can still not be used with the QA, since per definition the QA can only solve quadratic problems. Performing a quadratization of a high-order objective function ensures that it is rewritten as a quadratic-order function, with equivalent solutions.

There are many different methods of quadratization discussed in literature, an extensive overview of which is given by Dattani [34]. Some of these methods utilize auxiliary variables to rewrite the high-order objective function into an equivalent quadratic-order expression, while other methods are able to do so without the need for auxiliary variables. Each method has its respective benefits and drawbacks. For example, it is convenient when no auxiliary variables are needed, yet in that case it may require much effort to rewrite the objective function in an equivalent quadratic form. Alternatively, if a method uses auxiliary variables, it might be easier to find an equivalent quadratic form, but the additional variables increase the complexity of the objective function, making it more difficult to find the optimum [34].

In practice, the most straightforward way to perform the quadratization is to simply rely on the implementation that is provided by D-Wave [35]. In their implementation, all high-order terms are rewritten and replaced to be in terms of auxiliary variables, such that the final problem is at most of quadratic order. An additional user-defined parameter is used to select the strength with which the quadratization is enforced [35]. If the quadratization is not enforced correctly, this can result in a poor approximation of the original high-order objective function. The quadratization strength is problem-dependent and must be tuned such that the quadratization is always obeyed, to have an accurate representation of the original high-order objective function.

With the quadratization, the discrete truss sizing optimization problem is finally written as a QUBO problem. This vital step finally concludes all of the preparatory work that was necessary for the problem to be compatible with the quantum computing hardware. The next section will discuss the solution process for the discrete truss sizing optimization problems.

Solving the Discrete Truss Sizing QUBO

Having completed the previous processing steps, the truss sizing optimization problems can now finally be written in a QUBO formulation and can be solved using the QA. In this section, some notable parameters that influence the behavior of the QA are discussed, as well as the testing approach for understanding the performance of the QA for the three sample problems.

Overview of Analyses

To solve the reference truss problems, two different analysis methods are applied. First, brute-force evaluation of the original fractional objective function is used to obtain a baseline solution. Then, quantum annealing is used, following the procedures described in the previous sections. The specifications of the local classical computing hardware that was used in this research are given in Table 3.

DeviceLenovo Legion Y540-15IRH
CPUIntel Core i7-9750H 2.6 GHz
Memory16 GB DDR4 2667 MHz
GPUMobile NVIDIA RTX 2060 6GB

Table 3. Classical computing hardware.

The brute-force analyses will simply serve to obtain a reference solution to the truss sizing optimization problems. There are other more efficient (and more complicated) classical analysis methods available for truss optimization problems, as reviewed by Stolpe [36]. However, for the purposes of this study, simple brute-force analysis is sufficient to produce the reference solutions. Each of the brute-force analyses will be performed three times, so that an average solve time can be calculated.

The main focus for the QA analyses will be to find the computational time and the probability of obtaining the global optimum solution. It will also be measured how long the symbolic finite element approach takes to set up the original fractional objective function for the truss sizing optimization problems. The goal will be to find out whether it is feasible to apply quantum computing to these practical truss optimization problems. Furthermore, these analyses will show whether the methods outlined in the previous sections provide a feasible means of translating the truss sizing problem to a QUBO format. To calculate the average computational time and show a basic probability for finding the global optimum solution, the QA analyses are each performed ten times. The number of analyses could unfortunately not be increased due to limitations placed on the amount of quantum computational time allotted to basic user accounts on the D-Wave Leap platform.

Parameter Tuning

In the previous sections, a number of user-defined parameters were introduced that influence the objective functions of the three truss sizing problems. Values need to be chosen for these parameters before the problems can be submitted to the QA. Overall, the following parameters all need to be given values:

  • Iterative solving procedure

    • Maximum number of iterations allowed

    • Iteration convergence threshold

  • Objective function processing

    • Highest order terms allowed

    • Linear scaling magnitude

    • Non-linear scaling strength

    • Precision truncation magnitude

    • Unary constraint strength

    • Quadratization strength

  • Quantum annealing

    • Number of reads

    • Chain strength

To aid in finding sensible values for most of the above parameters, without wasting the limited amount of quantum computational time available, an alternative classical solver is used. D-Wave provides a Simulated Annealing (SA) solving algorithm, which, similar to their quantum annealer, can be used to solve QUBO problems. The main difference is that the SA solver only relies on the local classical computing hardware, and does not expend any of the quantum computational time allowance. The SA solver was therefore used to test the functionality of the Python code, and to find initial values for the relevant problem parameters.

Values for the parameters related to the iterative solving procedure were first chosen. Testing via initial trial SA analyses showed that around 5 iterations are needed to find a converged solution. This value will be tripled for the quantum annealing analyses to give some room for potential errors to be corrected during the procedure. Thus, the maximum number of iterations within one solving attempt will be set to 15. If the procedure does not converge after the maximum number of iterations is reached, the analysis is stopped, to prevent excessive expending of computational time. The convergence threshold δ\delta for the iterative procedure (as seen in eq. (23)) is set at a value of 10−610^{-6}, which is the same value used by Ajagekar et al.

Starting values for the different objective function processing parameters were also found from initial trial SA analyses. First of all, the highest order of terms allowed in the objective function for each of the sample problems will be set equal to the number of truss elements. Second, it was chosen to set the linear scaling maximum magnitude cuserc_{user} to a value of 1 for all analyses. Third, the non-linear scaling parameter cNLc_{NL} has been set to a value of 0.1 for all analyses. During brute-force testing it was seen that this value improves the distinction between minima in the energy landscapes for the sample problems, while preserving the global minima. Fourth, the unary constraint strength was set to a value of 10 for the two- and three-truss problems. For the four-truss problem it was set to a value of 20. Testing via SA showed that with these settings the constraint was obeyed consistently, yielding valid solutions to the truss sizing problems. Fifth, terms that have a magnitude smaller than 10−810^{-8} are truncated, to slightly reduce the number of terms in the objective functions. This is a conservative truncation, as it is well beyond the precision that the QA hardware can control. Finally, the quadratization strength is set to a value of 10 for the two- and three-truss problems, and a value of 20 for the four-truss problem, such that it equally matches the strength of the unary constraint.

For the QA, some additional parameters are needed to solve the sample problems. The number of reads describes the number of times a specific problem is solved by the QA, before the final best-performing solution is returned to the user. Increasing the number of reads increases the likelihood of obtaining optimal solutions, at the expense of additional computational time. To minimize the expenditure of quantum computational time, a viable number of reads was first estimated using the SA solver.

Using the SA solver, some tests were performed in which the number of reads was set to values of 16, 64, and 256, for each of the three sample problems. For the two-truss problem, the global optimum results were obtained every single time, regardless of the number of reads. For the three-truss problem, using 64 and 256 reads reliably gave optimal or near-optimal results. For the four-truss problem, only when setting the number of reads to 256 was the global optimum result reliably obtained.

The settings for the number of reads for the QA analyses were chosen based on the testing that was done using SA. Namely, for the two-truss problem, the number of reads will be set to 16 and 64. For the three-truss problem the number of reads will be set to 64 and 256. Finally, for the four-truss problem, the number of reads will only be set to 256.

The chain strength parameter for the QA relates to a physical issue called chain break, which can occur while the QA is solving problems. To explain the fine-tuning of the chain strength parameter, some additional context will first be given to explain the chain break phenomenon.

A QUBO problem is defined through an upper-triangular N×NN \times N matrix Q. The terms on the diagonal of the matrix Q relate only to a single problem variable, while the off-diagonal terms describe an interaction between two different problem variables. On the D-Wave 2000Q, which was used during this research, each qubit can only directly interact with at most six other qubits [3]. This limited connectivity between qubits can present an issue for larger QUBO problems.

When a QUBO is submitted to the QA, it must be embedded onto the physical architecture of the QPU. The embedding translates the logical structure of a QUBO problem and translates it to the physical structure of the QA. This also means that the logical problem variables are translated to physical qubits on the QPU. However, when the QUBO problem necessitates a high connectivity between logical problem variables it can become impossible to directly embed every logical variable onto individual single qubits. By chaining together strings of multiple qubits, and enforcing them to act as single logical problem variables, the connectivity between the embedded logical variables can be increased beyond the limitations of the physical hardware [37].

In practice, problems can become very challenging for the QA to solve if the number of interactions between variables is high. A QUBO problem with high connectivity requirements will lead to embeddings with very long qubit chains. In turn, the longer the qubit chains are, the more difficult it is to enforce the chained qubits to act in unison. When a qubit chain is working as intended, the chained qubits will all end up in the same final ground state, all being either 0 or 1. However, when a qubit chain is broken the qubits in the chain end up with a mix of 0 and 1 states. This makes the final state of the qubit chain, and the intended final state of the corresponding logical problem variable unclear. By increasing the chain strength, the risk of chain breaks occurring is reduced. However, overly high chain strength should be avoided as the relative strength of the objective function itself is reduced, potentially making it more difficult to obtain the true global optimum solution.

Initially, a chain strength of 10 was selected, but it was seen that chain breaks would still occur for the three- and four-truss problems. For those problems a chain strength of 30 performed better, preventing chain breaks from occurring. There are very many additional parameters that can be tuned to alter the performance of the quantum annealer, but these were left in their default configurations [38].

In Table 4 a summary is given of all parameters used for each of the analyses. Parameters that are irrelevant or not applicable for an analysis are indicated by NANA.

ParametersBrute-forceQuantum Annealing
Truss system2-truss3-truss4-truss2-truss3-truss4-truss
Total number of times analyzed333101010
Maximum number of iterationsNANANA151515
Iteration convergence thresholdNANANA10−610^{-6}10−610^{-6}10−610^{-6}
Number of reads per iterationNANANA{16,64}{64,256}{256}
Highest order terms allowedNANANA234
Linear scaling maximum magnitudeNANANA111
Non-linear scaling strengthNANANA0.10.10.1
Unary constraint strengthNANANA101020
Quadratization strengthNANANA101020
Precision truncation magnitudeNANANA10−810^{-8}10−810^{-8}10−810^{-8}
Chain strengthNANANA103030
Annealing time [usus]NANANA202020

Table 4. Parameters used for all analyses.

Results

Results: Two-Truss Problem

The two-truss problem is the simplest of the three sample problems. To set up the original fractional objective function for the problem, the symbolic finite element approach is used. For this problem, it took approximately 13.5 seconds to set up the fractional objective function. Once this objective function is found, it is written to a text file. The objective function is then imported and interpreted before performing every analysis, and no longer needs to be set up from scratch. This saves some time when performing the three brute-force analyses, and for the QA, where ten analyses are performed for each different setting of the number of reads.

For the brute-force analysis, evaluating the fractional objective function for valid solutions, an average of 0.234 seconds was needed to find the global optimum solution. The baseline global optimum solution is [0, 0, 1, 1, 0, 0]. This indicates the largest possible cross-sectional area should be chosen for the first truss element, while for the second truss element the smallest cross-sectional area should be chosen.

Using the QA, the analyses were performed ten times, to gain some insight into the probability of obtaining the globally optimal solution. In Figure 14, the solutions which were found by the QA are presented in a histogram. Superimposed on the histogram is a line-plot of the original fractional objective function, which had previously been calculated by brute force.

Figure 14. Solution probability histogram of two-truss problem using the QA, compared to original objective function. Global optimum solution located at solution number 7.

It can be seen from Figure 14 that, regardless of the choice for the number of reads, the QA finds solution number 7, which corresponds to the same global optimum solution as is obtained via the brute-force analyses.

When it comes to the computational time for the QA analyses, the following results were obtained:

  • With number of reads = 16

    • Average total time = 19.52 s. Standard deviation = 5.10 s.

    • Average QPU time = 59176 μs\mu\mathrm{s}. Standard deviation = 15061 μs\mu\mathrm{s}.

  • With number of reads = 64

    • Average total time = 19.06 s. Standard deviation = 0.21 s.

    • Average QPU time = 118207 μs\mu\mathrm{s}. Standard deviation = 10.7 μs\mu\mathrm{s}.

From these results it is seen that setting the number of reads to 64 leads to more consistent analysis times, compared to using only 16 reads. On the other hand, by setting the number of reads to 64, the amount of QPU access time is increased significantly.

Results: Three-Truss Problem

The three-truss problem is a more complicated problem to set up compared to the two-truss problem, due to the increased number of variables. Setting up the fractional objective function for this problem, and writing that expression to a text file took approximately 81.4 seconds. Once the expression was written to a file, it could simply be imported and reused for every analysis. Overall, three brute-force analyses were performed for the three-truss problem, as well as ten QA analyses for each setting of the number of reads.

Considering the brute-force analysis of the fractional objective function, it took an average of 0.9 seconds to find the global optimum solution [0,0,1,1,0,0,0,1]\left[0,0,1,1,0,0,0,1\right]. This solution indicates that the largest cross-sectional area should be chosen for the first and third truss elements, and that the smallest cross section should be chosen for the second truss element.

With the QA, the analyses were performed with the number of reads set to values of 64 and 256. The solution probability histogram in Figure 15 shows the results that were obtained. The figure also shows the original fractional objective function, as was calculated via brute-force. Analyses that ended with non-valid results are indicated by the ’NV’ column in the histogram.

Figure 15. Solution probability histogram of three-truss problem using the QA, compared to original objective function. Global optimum solution located at solution number 21.

From Figure 15, it can be seen that there is a large difference in performance, depending on the setting for the number of reads. Setting the number of reads to 64 leads to non-valid solutions for most analyses. At this setting, the QA does not reliably produce usable results. However, when the number of reads is increased to 256, optimal or near-optimal valid solutions are obtained most of the time. From these results it is also clear that the problem is more difficult for the QA to solve compared to the two-truss problem.

As part of the QA analyses, the following computational times were measured:

  • With number of reads = 64

    • Average total time = 98.7 s. Standard deviation = 37.5 s.

    • Average QPU time = 337477 μs\mu\mathrm{s}. Standard deviation = 117808 μs\mu\mathrm{s}.

  • With number of reads = 256

    • Average total time = 48.8 s. Standard deviation = 20.6 s.

    • Average QPU time = 558414 μs\mu\mathrm{s}. Standard deviation = 244331 μs\mu\mathrm{s}.

It is seen that setting the number of reads to 256 leads to more consistent behavior, as evidenced by the smaller standard deviation for the total analysis time. Furthermore, the higher number of reads allows for the analysis to converge more quickly, as fewer iterations are generally needed to find a solution. However, the consequence of choosing a higher number of reads is that the amount of QPU access time is also increased.

Results: Four-Truss Problem

The last problem, with the highest number of variables involved, is the four-truss problem. Using the symbolic finite element method, it took approximately 3431 seconds to set up the fractional objective function. This is a very significant increase compared to the roughly 81 seconds that were needed to set up the objective function of the three-truss problem. In this case, it is a great benefit that the fractional objective function is written to a text file. Testing of the analysis procedures is much faster when the objective function text file can simply be imported and interpreted, compared to prefacing every analysis by a nearly hour-long setup process. Overall, the brute-force analysis was performed three times, and the QA analysis was performed ten times with the number of reads set to 256.

Via brute-force analysis, the global optimum solution [1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0], was found in an average of 4.4 seconds. This solution indicates that the first, second, and fourth truss elements should optimally use the smallest choice for the cross-sectional area. The third truss element should use the largest available cross-sectional area.

The histogram of the results that were obtained by the QA are shown in Figure 16. The figure also shows a line plot of the original fractional objective function, which was determined by the brute-force analyses.

Figure 16. Solution probability histogram of four-truss problem using the QA, compared to original objective function. Global optimum solution located at solution number 7.

From Figure 16, it is seen that seemingly random, but valid, solutions are obtained by the QA. Only one solution was found that comes within 5% of the global optimum solution. Namely, solution number 34 was found once and has an an objective function value of 1.103. The global optimum solution is located at solution number 7, and has an objective function value of 1.065. It is worth noting that seven out of the ten analyses ended with an iteration run-out, rather than ending with a converged final solution.

The computational time for the QA analyses was obtained:

  • With number of reads = 256

    • Average total time = 437 s. Standard deviation = 39.0 s.

    • Average QPU time = 1280156 μs\mu\mathrm{s}. Standard deviation = 251109 μs\mu\mathrm{s}.

The average time to solve is approximately nine times longer than that for the three-truss problem, using the same number of reads. Furthermore, the average of 1.28 seconds of QPU access time per analysis meant that any further testing was not possible for this problem, as this would consume too much of the 60-second monthly QPU access budget.

Conclusions

This work has established a new method to apply QA to the discrete optimization of truss structures. A symbolic FEM approach is employed to express the objective function in terms of qubit variables. As the qubit variables encode the design choices of the truss structure, they would inevitably take part in the formulation of the stiffness matrix of the structure, which leads to a fractional form for the objective function. Ajagekar et al.'s iterative approach is used to approximate the original fractional objective function with a non-fractional one such that it can be made compatible with QA. The proposed method has been applied on three different discrete truss sizing optimization problems. It is found that the QA is able to find the global minimum solution if sufficient reads can be afforded. However, there are several challenges that need to be addressed for this approach to be scalable to larger problems.

Symbolic Finite Element Method

The first step to translating the truss sizing problems to a compatible format is to define an objective function, written in terms of binary variables. For this purpose the symbolic finite element method was used, which was implemented in Matlab. The time to setup the objective function for each of the three sample problems was measured, and is reiterated in Table 5.

Truss SystemVariablesSetup Time [s]Growth Factor
2613.504-
3981.3906.0270
4123430.54242.1494

Table 5. Overview of objective function setup time.

The timings given in Table 5 show that the symbolic finite element method implementation scales poorly as the number of problem variables increases. Even if the classical computing hardware used for this method improves, this method is likely infeasible for larger problems. While the symbolic finite element method allows the practical application of quantum annealing to be investigated for simple truss sizing problems, the current implementation cannot be directly applied to larger and more realistic truss structures.

Further research is needed to investigate more efficient ways of solving symbolic system equations.

Fractional Objective Function

When the symbolic finite element method is used to set up an objective function for a discrete truss sizing optimization problem, the resulting objective function has a fractional form. This further complicates the journey to achieving a QUBO compatible form. An iterative method was implemented that rewrites the original fractional objective function into a non-fractional form. This non-fractional function can then be further processed in order to achieve the final QUBO problem. However, a number of points make the current implementation difficult to use on the QA hardware.

Firstly, the objective function that is obtained from the symbolic finite element method contains all possible multiplications between the available binary variables. This means that the problem initially requires an all-to-all connectivity between qubits, if it was to be directly embedded on the QPU. This research describes a number of steps that were taken to reduce the complexity of the truss sizing problem, such as removing excessively high-order terms, and truncating insignificant terms. Nevertheless, the connectivity requirements for the truss sizing problems remain far beyond the natural capability of the QA, meaning that long qubit chains are needed to embed the truss sizing problems. Not only do these long qubit chains have a negative impact on the performance of the QA, but larger truss sizing problems could eventually become infeasible to embed on the QPU, as the problem requirements could easily outgrow the physical capabilities of the QA hardware.

Secondly, as the symbolic finite element method yields a fractional objective function, the current approach relies on an iterative scheme in order to translate the objective function to a QUBO format. This means that various sources of overhead are repeatedly added to the solving process: repeatedly processing new non-fractional objective functions, waiting for an embedding to be calculated, awaiting your turn in the D-Wave problem submission queue, waiting to obtain the results from D-Wave, and repeatedly going through potentially inefficient Python programming. All of this contributes to the long total solve time, particularly for larger problems.

Quantum Annealing

When finally the objective function is successfully translated to a QUBO compatible form, it is submitted to the D-Wave QA to obtain a solution. From the results obtained for the three sample problems, it is seen that the QA has increasing difficulty in finding optimal or near-optimal solutions as the problem gets larger. For the largest sample problem, the optimum solution was not found within the allowable QPU time. More reads and longer QPU calculation time will be expected to find the solution.

Overall, the method proposed in this research constitutes a proof-of-concept in using QA for discrete structural optimization. The concepts of setting up a symbolic objective function, finding ways to simplify an objective function, and eventually translating a problem to a QUBO format may also be applicable to other optimization problems on QA, particularly when the qubit variables form part of the stiffness matrix and a fractional objective function needs to be evaluated. The identified challenges requires further research effort to improve its scalability onto larger problems.

Author Contributions: Conceptualization, K. Wils and B. Chen; methodology, K. Wils and B. Chen; software, K. Wils; validation, K. Wils and B. Chen; formal analysis, K. Wils; investigation, K. Wils; resources, K. Wils; data curation, K. Wils; writing—original draft preparation, K. Wils; writing—review and editing, B. Chen; visualization, K. Wils; supervision, B. Chen; project administration, B. Chen; All authors have read and agreed to the published version of the manuscript.

Funding: This research received no external funding.

Institutional Review Board Statement: Not applicable.

Informed Consent Statement: Not applicable.

Data Availability Statement: All Python and Matlab code produced during this research, as well as the results that were obtained, are publicly available [27].

Acknowledgments: The authors would like to acknowledge the intellectual discussions with Mr. Giorgio Tosti Balducci, PhD candidate in the same department, during this project.

Conflicts of Interest: The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

AbbreviationMeaning
MDPIMultidisciplinary Digital Publishing Institute
DOAJDirectory of open access journals
QAQuantum Annealer
GPQCGeneral Purpose Quantum Computer
QPUQuantum Processing Unit
QUBOQuadratic Unconstrained Binary Optimization
FEMFinite Element Method
SASimulated Annealing

Table 6.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

References

  1. [1]Nielsen, M.A.; Chuang, I.L. Quantum Computation and Quantum Information: 10th Anniversary Edition; Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667.
  2. [2]Montanaro, A. Quantum algorithms: an overview. npj Quantum Information 2016, 2. https://doi.org/10.1038/npjqi.2015.23.
  3. [3]D-Wave Systems Inc.. Getting Started with the D-Wave System: User Manual, 2018.
  4. [4]Denchev, V.S.; Boixo, S.; Isakov, S.V.; Ding, N.; Babbush, R.; Smelyanskiy, V.; Martinis, J.; Neven, H. What is the Computational Value of Finite-Range Tunneling? Phys. Rev. X 2016, 6, 031015. https://doi.org/10.1103/PhysRevX.6.031015.
  5. [5]Zheng, Y.; Song, C.; Chen, M.C.; Xia, B.; Liu, W.; Guo, Q.; Zhang, L.; Xu, D.; Deng, H.; Huang, K.; et al. Solving Systems of Linear Equations with a Superconducting Quantum Processor. Phys. Rev. Lett. 2017, 118, 210504.DOI
  6. [6]Neukart, F.; Compostella, G.; Seidel, C.; von Dollen, D.; Yarkoni, S.; Parney, B. Traffic flow optimization using a quantum annealer. arXiv e-prints 2017, p. arXiv:1708.01625, [arXiv:quant-ph/1708.01625].arxiv.org/abs/1708.01625
  7. [7]Van Vreumingen, D.; Neukart, F.; Von Dollen, D.; Othmer, C.; Hartmann, M.; Voigt, A.C.; Bäck, T. Quantum-assisted finite-element design optimization. arXiv e-prints 2019, p. arXiv:1908.03947, [arXiv:quant-ph/1908.03947].arxiv.org/abs/1908.03947
  8. [8]Stollenwerk, T.; O’Gorman, B.; Venturelli, D.; Mandrà, S.; Rodionova, O.; Ng, H.; Sridhar, B.; Rieffel, E.G.; Biswas, R. Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management. IEEE Transactions on Intelligent Transportation Systems 2019, pp. 1–13.
  9. [9]Van der Linde, S.; Neumann, N. Hybrid Classical-Quantum Computing in Geophysical Inverse Problems: The Case of Quantum Annealing for Residual Statics Estimation. In Proceedings of the Sixth EAGE High Performance Computing Workshop. EAGE Publications BV, 2022, Vol. 2022, pp. 1–5.DOI
  10. [10]Ye, Z.; Qian, X.; Pan, W. Quantum Topology Optimization via Quantum Annealing. IEEE Transactions on Quantum Engineering 2023.arxiv.org/abs/2301.11531
  11. [11]Lee, D.; Shon, S.; Lee, S.; Ha, J. Size and Topology Optimization of Truss Structures Using Quantum-Based HS Algorithm. Buildings 2023, 13, 1436.DOI
  12. [12]Sandt, R.; Le Bouar, Y.; Spatschek, R. Quantum annealing for microstructure equilibration with long-range elastic interactions. Scientific Reports 2023, 13, 6036.
  13. [13]Tosti Balducci, G.; Chen, B.; Möller, M.; Gerritsma, M.; De Breuker, R. Review and perspectives in quantum computing for partial differential equations in structural mechanics. Frontiers in Mechanical Engineering 2022, p. 75.
  14. [14]Bayerstadler, A.; Becquin, G.; Binder, J.; Botter, T.; Ehm, H.; Ehmer, T.; Erdmann, M.; Gaus, N.; Harbach, P.; Hess, M.; et al. Industry quantum computing applications. EPJ Quantum Technology 2021, 8, 25.DOI
  15. [15]Bova, F.; Goldfarb, A.; Melko, R.G. Commercial applications of quantum computing. EPJ quantum technology 2021, 8, 2.DOI
  16. [16]Airbus. Airbus Quantum Computing Challenge: Bringing flight physics into the Quantum Era. Online, 2019. Accessed: 2019-11-06.
  17. [17]Volkswagen. Volkswagen optimizes traffic flow with quantum computers . Online, 2019. Accessed: 2020-09-04.
  18. [18]Glover, F.; Kochenberger, G.; Du, Y. A Tutorial on Formulating and Using QUBO Models. arXiv e-prints 2018, p. arXiv:1811.11538, [arXiv:cs.DS/1811.11538].arxiv.org/abs/1811.11538
  19. [19]Johnson, M.W.; Amin, M.H.S.; Gildert, S.; Lanting, T.; Hamze, F.; Dickson, N.; Harris, R.; Berkley, A.J.; Johansson, J.; Bunyk, P.; et al. Quantum annealing with manufactured spins. Nature 2011, 473, 194–198.DOI
  20. [20]Boixo, S.; Albash, T.; Spedalieri, F.M.; Chancellor, N.; Lidar, D.A. Experimental signature of programmable quantum annealing. Nature Communications 2013, 4.DOI
  21. [21]Borle, A.; Lomonaco, S.J. Analyzing the quantum annealing approach for solving linear least squares problems. In Proceedings of the International Workshop on Algorithms and Computation. Springer, 2019, pp. 289–301.arxiv.org/abs/1809.07649
  22. [22]Shin, S.W.; Smith, G.; Smolin, J.A.; Vazirani, U. How “Quantum” is the D-Wave Machine? arXiv e-prints 2014, p. arXiv:1401.7087, [arXiv:quant-ph/1401.7087].arxiv.org/abs/1401.7087
  23. [23]Lucas, A. Ising formulations of many NP problems. Frontiers in Physics 2014, 2.DOI
  24. [24]Biswas, R.; Jiang, Z.; Kec̆ęzhi, K.; Knysh, S.; Mandrà, S.; O’Gorman, B.; Perdomo-Ortiz, A.; Petukhov, A.; Realpe-Gómez, J.; Rieffel, E.; et al. A NASA perspective on quantum computing: Opportunities and challenges. Parallel Computing 2017, 64, 81–98.DOI
  25. [25]McGeoch, C.C.; Harris, R.; Reinhardt, S.P.; Bunyk, P.I. Practical Annealing-Based Quantum Computing. Computer 2019, 52, 38–46.DOI
  26. [26]McGeoch, C.C. Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice. Vol. 5, Morgan & Claypool Publishers LLC, 2014; pp. 1–93.DOI
  27. [27]Wils, K. Truss Sizing Optimization: Symbolic Finite Element Method QUBO Repository, 2020. https://doi.org/10.34894/PYZGEX.
  28. [28]Ajagekar, A.; Humble, T.; You, F. Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems. arXiv e-prints 2019, p. arXiv:1910.13045, [arXiv:quant-ph/1910.13045].DOI
  29. [29]D-Wave Systems Inc. Technical Description of the D-Wave Quantum Processing Unit, 2020.
  30. [30]D-Wave Systems Inc.. QPU Properties: D-Wave 2000Q Online System (DW_2000Q_2_1), 2019.
  31. [31]Lucas, A. Hard combinatorial problems and minor embeddings on lattice graphs. Quantum Information Processing 2019, 18, 203, [arXiv:quant-ph/1812.01789].arxiv.org/abs/1812.01789
  32. [32]Kochenberger, G.; Hao, J.K.; Glover, F.; Lewis, M.; Lü, Z.; Wang, H.; Wang, Y. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization 2014, 28, 58–81.DOI
  33. [33]Vyskočil, T.; Pak, S.; Djidjev, H.N. Embedding Inequality Constraints for Quantum Annealing Optimization. In Quantum Technology and Optimization Problems; Springer International Publishing, 2019; pp. 11–22.
  34. [34]Dattani, N. Quadratization in discrete optimization and quantum mechanics. arXiv e-prints 2019, p. arXiv:1901.04405, [arXiv:quant-ph/1901.04405].arxiv.org/abs/1901.04405
  35. [35]D-Wave Systems Inc. dimod.higherorder.utils.make_quadratic. Online, 2017. Accessed: 2020-07-08.
  36. [36]Stolpe, M. Truss optimization with discrete design variables: a critical review. Structural and Multidisciplinary Optimization 2016, 53, 349–374.DOI
  37. [37]Fang, Y.L.; Warburton, P.A. Minimizing minor embedding energy: an application in quantum annealing. arXiv e-prints 2019, p. arXiv:1905.03291, [arXiv:quant-ph/1905.03291].arxiv.org/abs/1905.03291
  38. [38]D-Wave Systems Inc. D-Wave Solver Properties and Parameters Reference, 2020.

Paper details

vlnc:W_47wphmw2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents