# Cutting-Edge Trajectory Optimization through Quantum Annealing
## 2 Quantum Annealing Optimization
The energy of the Ising model is expressed by the following equation: \[J_{I}(\sigma)=\sum_{i}a_{i}\sigma_{i}+\sum_{i<j}b_{ij}\sigma_{i}\sigma_{j}.\] (5) In Equation (5), \(a_{i}\) represents the linear coupling coefficients for individual spins, while \(b_{ij}\) represents the coupling coefficients for pairs of spins. The first sum accounts for the energy associated with the individual spin states, whereas the second sum reflects the energy due to interactions between spins. * _QUBO Formulation_ is a powerful representation of optimization problems using a quadratic function of binary variables. We consider a problem with n binary variables denoted as \(x=(x_{1},x_{2},\ldots,x_{n})\), where each \(x_{i}\) can take either zero or one. The objective is to minimize the following quadratic function: \[J_{q}(x)=x^{T}Qx.\] (6) In Equation (6), \(x^{T}\) represents the transpose of the binary variable vector \(x\), and \(Q\) is an \(n\times n\) matrix of coefficients. The goal is to find the assignment of binary values to \(x\) that minimizes quadratic function \(J_{q}(x)\). This formulation is widely used in QA to transform complex optimization problems into a format compatible with quantum systems. The Ising and QUBO formulations are closely related through a simple transformation that maps Ising spins (\(\sigma_{i}\)) to binary variables (\(x_{i}\)). In the Ising Formulation, the linear coupling coefficients (\(a_{i}\)) are transformed into the diagonal components of matrix \(Q\) in the QUBO Formulation, while the coupling coefficients for pairs of spins (\(b_{ij}\)) are represented by the off-diagonal components. It is important to recognize that these formulations are mathematical abstractions designed to conveniently express optimization problems in a general format. When implementing an optimization problem on a real quantum annealer, the possible mismatch between the logical lattice of the problem (how the variables mathematically interact with each other) and the physical connectivity pattern (how the qubits are actually connected with each other in the annealer) must be taken into account. In fact, quantum annealers are built with a specific graph topology that dictates which qubits are physically connected with other qubits. If the logical graph of the problem does not match the physical graph of the machine, a procedure called embedding must be employed to adapt the first to the second. The embedding works by creating chains of qubits in the physical graph that are forced to behave as a single variable, always assuming the same value; through these chains, it is possible to connect qubits not physically connected in the annealer topology and crafting an embedded optimization problem equivalent to the starting one. As an extremely simple schematic to illustrate the concept, in Figure 1,a logical graph is shown where three variables (represented as circles) interact as follows: Variable 1 interacts with Variables 3 and 4. On the other hand, the physical graph, on the right, does not provide a connection between Qubits 1 and 4. Therefore, a possible embedding is to create a chain including Qubits 2 and 4, such that Connection 1-4 can now be implemented exploiting Connections 1-2 and 2-4. We notice that, although the logical problem includes three variables, the embedded problem must use four qubits; therefore, the embedding procedure comes at the cost of increasing the number of qubits needed to tackle the problem. As a consequence, a problem that requires embedding could require an annealer with a number of qubits much larger than the number of variables. Moreover, utilizing longer chains in the embedding can increase susceptibility to noise and errors. Longer chains may become fragile, leading to potential disruptions that adversely affect the quality and reliability of the solution. Addressing these challenges is critical to unlocking the full potential of QA for solving complex optimization problems and realizing the transformative power of quantum computing.