Doctoral Program

In Information Technologies and the application to Management, Architecture
and Geophysics.
La Salle - Ramon Llull University

Candidate name:
Parfait Atchadé Adélomou

Title:
Quantum Algorithms for solving Hard Constrained Optimisation Problems

Supervisor 1 name:
Dra. Elisabet Golobardes Ribé

Supervisor 2 name:
Dr. Xavier Vilasís-Cardona

#### Acknowledgements

To Martina and Africa

This PhD thesis research has resulted from numerous encounters, experiences,
consultations, conferences, networking, friendships and sleepless nights.
There are many people to whom I owe a high debt of gratitude for their
invaluable inspiration, comments, critiques, corrections, and references. All
of which makes for an incredible and unforgettable academic culmination that
now, notably and sadly, reaches the end after three years of hard, challenging
and sometimes lonely research.

For this, one of my most sincere and profound thanks goes to the IBMQ team,
especially to the aqua division represented by Steve Wood. For two years of
correspondence, comments and technical exchange, we have come to understand
many concepts and, above all feel, we are wrapped in a community that gave us
all the facilities to achieve our goal. To Simone Severini from AWS-Braket for
his support to achieve our goal and to the quantum community and people I met
during this quantum mechanics and computing journey.

I make a special dedication to Martina to find a door to the quantum world
through this work. A hope to understand and correctly model our environment
and to have a tool to understand some of the problems or diseases that today
have no cure. To Jenny, tireless, loving, respectful and helpful for all the
tangible and intangible details to achieve this result. It reminds me of
Bell’s inequality; Two entangled particles, before the measurement, and even
at an immeasurable distance, modifying one, the other remains faithful to the
effects of the first and vice versa.

To Africa, since it will be, I believe, one of the indisputable pillars of
quantum computing.

This thesis work is not the end but the beginning of a long journey in the
quantum world.

I want to be open to any reader, researcher who wishes to share their point of
view with me at<EMAIL_ADDRESS>
Thank you

Parfait Atchadé Adélomou

Barcelona 18 August 2021

#### Abstract

The thesis deals with Quantum Algorithms for solving Hard Constrained
Optimization Problems. It shows how quantum computers can solve difficult
everyday problems such as finding the best schedule for social workers or the
path of a robot picking and batching in a warehouse. The path to the solution
has led to the definition of a new artificial intelligence paradigm with
quantum computing, quantum Case-Based Reasoning (qCBR) and to a proof of
concept to integrate the capacity of quantum computing within mobile robotics
using a Raspberry Pi 4 as a processor (qRobot), capable of operating with
leading technology players such as IBMQ, Amazon Braket (D-Wave) and Pennylane.
To improve the execution time of variational algorithms in this NISQ era and
the next, we have proposed EVA: a quantum Exponential Value Approximation
algorithm that speeds up the VQE, and that is, to date, the flagship of the
quantum computation.

###### Contents

  1. I State of the Art
    1. 1 Introduction
      1. 1.1 Motivation
      2. 1.2 Work context
      3. 1.3 Goals
      4. 1.4 Hypothesis
      5. 1.5 Development of the thesis
      6. 1.6 Thesis structure
    2. 2 Combinatorial Optimisation problems
      1. 2.1 Introduction
      2. 2.2 Travelling Salesman Problem
        1. 2.2.1 Constructive heuristics
      3. 2.3 Job Shop Scheduling Problems
      4. 2.4 Vehicle Routing Problem
      5. 2.5 Summary
    3. 3 Systems and useful concepts
      1. 3.1 Introduction
      2. 3.2 Hamiltonian path and cycles
      3. 3.3 Ising model and the Hamiltonian
      4. 3.4 Summary
    4. 4 Solving combinatorial optimisation problems
      1. 4.1 Introduction
      2. 4.2 Linear Programming
        1. 4.2.1 The Objective function, decision variables and the constraints
        2. 4.2.2 Formulation of linear programming of binary integers
      3. 4.3 Quadratic Programming
        1. 4.3.1 Quadratic Formulation
        2. 4.3.2 Change of variables to simplify the quadratic formulation
      4. 4.4 Quadratic programming with quadratic constraints
      5. 4.5 Summary
    5. 5 Introduction Quantum Mechanics
      1. 5.1 Introduction
      2. 5.2 Moore Law
        1. 5.2.1 State of the Quantum Technologies
      3. 5.3 Noisy Intermediate-Scale Quantum
      4. 5.4 Postulate 1
      5. 5.5 Postulate 2
        1. 5.5.1 Postulate 2’
      6. 5.6 Postulate 3
      7. 5.7 Postulate 4
      8. 5.8 Summary
    6. 6 Complexity Class
      1. 6.1 Introduction
      2. 6.2 Quantum complexity
      3. 6.3 The deterministic Turing machine
      4. 6.4 The probabilistic Turing machine.
      5. 6.5 Quantum Turing Machine
      6. 6.6 Study of complexity
      7. 6.7 Summary
    7. 7 Quantum Gates
      1. 7.1 Introduction
      2. 7.2 General U-gate
      3. 7.3 Single qubit gates
      4. 7.4 Gate I
      5. 7.5 Gate NOT
      6. 7.6 Gate Y
      7. 7.7 Gate Z
      8. 7.8 The Pauli Operators
      9. 7.9 Hadamard gate
      10. 7.10 Gate $R_{\phi}$
      11. 7.11 Gate T
      12. 7.12 Gate S
      13. 7.13 More than one qubit system.
      14. 7.14 Toffoli gate
      15. 7.15 Summary
    8. 8 Quantum Computers
      1. 8.1 Introduction
      2. 8.2 Simulated annealing
      3. 8.3 Quantum annealing
        1. 8.3.1 Quantum Tunneling
      4. 8.4 Quantum Computers
        1. 8.4.1 Quantum gate-based computers
        2. 8.4.2 Quantum annealing-based computers
      5. 8.5 summary
    9. 9 Quantum Computing
      1. 9.1 Introduction
        1. 9.1.1 Quadratic Unconstrained Binary Optimisation Problems
      2. 9.2 Variational calculation
        1. 9.2.1 Variational Quantum Eigensolver
        2. 9.2.2 Noisy VQE for the Optimisation problem
        3. 9.2.3 Quantum approximate optimisation algorithm
      3. 9.3 Summary
  2. II Contributions
    1. 10 Research Design
      1. 10.1 Introduction
      2. 10.2 Proposed problem
      3. 10.3 Experimentation tools
        1. 10.3.1 Programming environments
          1. 10.3.1.1 PennyLane:
          2. 10.3.1.2 Cirq
          3. 10.3.1.3 Qsharp
          4. 10.3.1.4 IBM Quantum Experience
        2. 10.3.2 Experimentation algorithms
          1. 10.3.2.1 SPSA
          2. 10.3.2.2 SLSQP
          3. 10.3.2.3 COBYLA
        3. 10.3.3 Variational Quantum Algorithms Experimentation
        4. 10.3.4 CPLEX
        5. 10.3.5 DOCPLEX
      4. 10.4 Summary
    2. 11 Approaches to solve the SWP
      1. 11.1 Introduction
      2. 11.2 Social Workers Problem based on a new VRPTW
        1. 11.2.1 Social Workers’ Problem based on a QUBO approach
        2. 11.2.2 The algebraic approach of the SWP formulation
        3. 11.2.3 Vectorisation form of our formulation
        4. 11.2.4 Mapping the SWP’s formulation into a list of Pauli operators
          1. 11.2.4.1 Mapping of quadratic variables of the Hamiltonian in the Z-basis.
          2. 11.2.4.2 Coding the Hamiltonian into the Pauli Operators
          3. 11.2.4.3 Quantum solution from the ground up and closer to the Quantum Native form.
        5. 11.2.5 Resolution of our formulation with docplex
        6. 11.2.6 CPLEX solver
        7. 11.2.7 Solving our Quantum SWP with MinimumEigenOptimiser
        8. 11.2.8 Solving our quantum SWP by using the ADMM Optimiser
        9. 11.2.9 Backtracking
        10. 11.2.10 First approach of the SWP’s generalisation
      3. 11.3 Research Results
        1. 11.3.1 Experimentation
      4. 11.4 Discussions
      5. 11.5 Benchmarks of SWP
        1. 11.5.1 Comparing VQE solution with classical solver
        2. 11.5.2 Backtracking
        3. 11.5.3 Comparison of the algorithms’ complexity
        4. 11.5.4 OR Tool SAT
        5. 11.5.5 Comparing 10 scenarios of SWP with VQE
          1. 11.5.5.1 Comparing 5 scenarios of SWP with VQE and QAOA
        6. 11.5.6 Comparing 10 scenarios of SWP on VQE and QAOA
        7. 11.5.7 Comparing 10 banks of the Social Workers’ schedules on QAOA
        8. 11.5.8 Comparing the SWP on all quantum algorithms
      6. 11.6 Conclusion and Further Work
        1. 11.6.1 Conclusions
        2. 11.6.2 Future directions
      7. 11.7 Summary
    3. 12 The quantum CBR (qCBR)
      1. 12.1 Introduction
        1. 12.1.1 Related Work
      2. 12.2 Case-Based Reasoning
      3. 12.3 Implementation
      4. 12.4 Quantum classifiers
      5. 12.5 Variational Quantum Classifier
        1. 12.5.1 The Ansatz
          1. 12.5.1.1 Fidelity cost function
      6. 12.6 Details of qCBR
        1. 12.6.1 Memory Structure
      7. 12.7 Results
      8. 12.8 Discussions
      9. 12.9 Conclusions and further work
      10. 12.10 Summary
    4. 13 The qRobot: generalising the SWP
      1. 13.1 Introduction
      2. 13.2 Work Context
      3. 13.3 Implementation
        1. 13.3.1 The problem’s formulation
        2. 13.3.2 Picking and Batching formulation
        3. 13.3.3 Mapping the classical to quantum optimisation
      4. 13.4 qRobot Results
      5. 13.5 Discussions
      6. 13.6 Conclusions and further work
      7. 13.7 Summary
  3. III Conclusions
    1. 14 Results
      1. 14.1 Introduction
      2. 14.2 Discussion
      3. 14.3 Conclusions and Further Work
        1. 14.3.1 Conclusions
        2. 14.3.2 Further Work
        3. 14.3.3 International contribution and talent pool
        4. 14.3.4 Schedule/Work plan
        5. 14.3.5 Pedagogical contribution
        6. 14.3.6 Contribution to business vision
        7. 14.3.7 Lessons learned (Hard Skills)
        8. 14.3.8 Consolidated skills (Soft Skills)

#### List of Publications

  * $\diamond$

The results of this thesis have been made public in seven papers.

* Atchade-Adelomou P., Golobardes Ribé E., Vilasís Cardona X. (2020) Using the Variational-Quantum-Eigensolver (VQE) to Create an Intelligent Social Workers Schedule Problem Solver. In: de la Cal E.A., Villar Flecha J.R., Quintián H., Corchado E. (eds) Hybrid Artificial Intelligent Systems. HAIS 2020. Lecture Notes in Computer Science, vol 12344. Springer, Cham. https://doi.org/10.1007/978-3-030-61705-9_21

* Atchade-Adelomou P., Golobardes Ribé E., Vilasís Cardona X. Formulation of the social workers’ problem in quadratic unconstrained binary optimization form and solve it on a quantum computer. Journal of Computer and Communications. 2020 Nov 5;8(11):44-68. DOI: 10.4236/jcc.2020.811004

* Atchade-Adelomou P., Alonso-Linaje G, Albo-Canals J, Casado-Fauli D. qRobot: A Quantum computing approach in mobile robot order picking and batching problem solver optimization. MDPI AG, vol 14, number = 7, pages = 194, 2021 May 11. Algorithms, url = https://doi.org/10.3390/a14070194

* Atchade-Adelomou P, Casado-Fauli D, Golobardes Ribé E, Vilasís Cardona X. quantum Case-Based Reasoning (qCBR). arXiv preprint arXiv:2104.00409. 2021 Apr 1.

* Atchade-Adelomou P., Golobardes Ribé E., Vilasís Cardona X. Using the Parameterized Quantum Circuit combined with Variational-Quantum-Eigensolver (VQE) to create an Intelligent social workers’ schedule problem solver. arXiv preprint arXiv:2010.05863. 2020 Oct 12.

* Atchade-Adelomou P., Alonso-Linaje G. Quantum Enhanced Filter: QFilter. arXiv preprint arXiv:2104.03418. 2021 Apr 7.

* Alonso-Linaje G, Atchade-Adelomou P. EVA: a quantum Exponential Value Approximation algorithm. arXiv preprint arXiv:2106.08731. 2021 Jun 16.

###### List of Figures

  1. 3.1 Shows a graph of 26 vertices in which a Hamiltonian cycle is highlighted
  2. 3.2 A Lattice in the Euclidean plane [LatticeGraph]
  3. 3.3 Five Lattices in the Euclidean plane [LatticeGraph]
  4. 4.1 Variable change to simplify quadratic programming
  5. 5.1 TBluefors dilution refrigerators used in the MIT Engineering Quantum Systems group to operate superconducting qubits at near-zero temperatures [213]
  6. 5.2 Moore law Roadmap: Quantum Computing Stack Exchange [178]
  7. 5.3 The number of research papers published per year in quantum computing and technologies [198]
  8. 5.4 Quantum Computing is becoming the talk of the town [3]
  9. 5.5 The number of qubits achieved by date and organisation. Roadmap by YOLE Development [84]
  10. 5.6 Metrics and milestones to help monitor the development of quantum computing. Roadmap by MIT [198]
  11. 5.7 Companies and startups involved in the 2018 quantum computing ecosystem. Roadmap by Quantum World Association
  12. 5.8 Observability of a classical system
  13. 5.9 Observability of a quantum system
  14. 6.1 The conjectured evolution of the quantum complexity of the operator $e^{iHt}$ [30]
  15. 7.1 One-qubit circuit of quantum gate association to illustrate unit transformation matrix $U$
  16. 7.2 Circuit of the Quantum Identity gate $I$
  17. 7.3 The Circuit of the quantum Pauli’s first gate if we do not consider gate I
  18. 7.4 Circuit of the quantum gate Y. The second gate of Pauli
  19. 7.5 Circuit of the quantum gate Z. Third gate of Pauli
  20. 7.6 Hadamard Gate Circuit. A significant gate to get the superposition
  21. 7.7 A circuit in Qiskit of the operation equivalent to $HZH=X$
  22. 7.8 $R_{\phi}$ Gate of a qubit. This gate is significant for rotational operations
  23. 7.9 $T$ Gate of one qubit. Remember that the inverse of this gate is not itself
  24. 7.10 $S$ Gate of one qubit. Remember that the inverse of this gate is not itself
  25. 7.11 A 3-qubit system where we apply a Hadamard gate to each qubit. With this application, we assign each of the input qubits with the same probability
  26. 7.12 The two qubits $C_{NOT}$ gate
  27. 7.13 The Toffoli gate implemented with 2 $C_{NOT}$ gate, 2 $R_{\phi|\phi=\pi}$ gates and another gate $R_{\phi|\phi=-\pi}$.
  28. 7.14 The Toffoli gate implemented with both the controlled-Hadamard and controlled-Z gates, which can be implemented with a single $C_{NOT}$.
  29. 8.1 The quantum computing ecosystem [77]
  30. 8.2 Simulated annealing concept. The motion described by the particle but viewed uphill is described as a thermal jump. This is because Simulated annealing is a physics algorithm that mimics the behaviour of materials as they cool slowly. The ”walker” is like an atom in a metal driven by temperature to reconfigure itself. These changes are random but are more likely to move to lower energy settings than higher energy configurations. That is why it is said that the ”walker” follows a biased random movement.
  31. 8.3 Advantage of quantum tunnelling over thermal jump taking advantage of the Simulated Annealing concept
  32. 8.4 one-dimensional potential barrier
  33. 8.5 Full-Stack execution [38]
  34. 8.6 compiler infrastructure [38]
  35. 8.7 An example of general-purpose quantum microarchitecture [38]
  36. 8.8 Example of experimental implementation of microarchitecture for (real) superconducting qubits [38]
  37. 8.9 Example of the new microarchitecture for the quantum genome sequencing accelerator [38]
  38. 8.10 Microsoft Quantum Computer [99].
  39. 8.11 IBM Quantum Computer [12].
  40. 8.12 Xanadu Quantum Computer [48].
  41. 8.13 Inside D-Wave Quantum Computer [98]
  42. 8.14 The challenge of simulating transmon quantum processors [137]
  43. 8.15 Microsoft Quantum Development Kit. Provides an end-to-end scalable quantum development environment and leverages the Q# quantum programming language, which enables users to design, compile, and simulate quantum algorithms [MS].
  44. 9.1 Adaptative Variational Quantum Eigensolver [107].
  45. 9.2 Architecture of the Variational Quantum Eigensolver. The architecture of the quantum-variational eigensolver. Algorithm 1: Quantum states that have been previously prepared are fed into the quantum modules, which compute $\langle H_{i}\rangle$, where $H_{i}$ is any given term in the sum defining H. The results are passed to the CPU, which computes $\langle H\rangle$. Algorithm 2: The classical minimisation algorithm, run on the CPU, takes $\langle H\rangle$ and determines the new state parameters, which are then fed back to the QPU.
  46. 9.3 Minimisation principle used in Variational Quantum Eigensolvers to empower Quantum Machine Learning.
  47. 9.4 From Annealing to QAOA. These graphs conceptually show us the differences/evolution between quantum annealing (left) that follows this adiabatic time evolution path. Simulated annealing (middle) follows the same way in discrete steps and QAOA that follows adiabatic time evolution path in p steps. These define the accuracy of the solution.
  48. 9.5 QAOA algorithm operation.The system is initialised along the y-direction in the Bloch sphere in the $|+\rangle^{\otimes N}$ state. The unitary evolution under $H=X_{0}+Y_{1}+Z_{2}$ is implemented for $\gamma_{i}\beta_{i}$ angles for p times. At the end of the algorithm, global measurements in the x and the y basis are performed to compute the average energy $\langle H\rangle=E(\overrightarrow{\gamma},\overrightarrow{\beta})$, which is compared to the theoretical ground state energy $E_{\text{groundstate}}$.
  49. 9.6 QAOA’s diagram process to perform it experimentally with quantum devices. In our study, 1000 samples are used to estimate the value of the cost function $E(\overrightarrow{\gamma},\overrightarrow{\beta})=\langle\overrightarrow{\gamma},\overrightarrow{\beta}|H|\overrightarrow{\gamma},\overrightarrow{\beta}\rangle$ at each variational iteration.
  50. 10.1 My research’s path over these 3 years
  51. 10.2 Using the Variational-Quantum-Eigensolver (VQE) as Quantum Machine Learning (QML) to creates an Intelligent social workers schedule problem solver.
  52. 10.3 Overview of all published quantum computing programming environments [91].
  53. 10.4 Detailed characteristics of all published quantum computing programming environments. Data, August 2018 [91].
  54. 10.5 Xanadu bets with its PennyLane platform [37].
  55. 10.6 Google bets with its Cirq platform.
  56. 10.7 Bet on Microsoft with its Qsharp platform [QC˙MS].
  57. 10.8 Azure Quantum Computing [MS].
  58. 10.9 The heat map on the results of analysis and documentation.
  59. 10.10 Results of the evaluation for the community analysis. For each project, we indicate whether there is a public development roadmap and whether the software is published in the form of releases. Besides, we report the GitHub community profile score, the total number of contributors, the type of discussion channel focused on the user and the developer, and the type of public code review process, specifically if it applies to internal (I) external (E) taxpayers. Data were obtained in August 2018 [91].
  60. 10.11 Evaluation results for the static analysis of each project and its source code [91].
  61. 10.12 Components of Qiskit’s framework [217].
  62. 10.13 IBMQ User Profile.
  63. 10.14 IBMQ Circuit Composer.
  64. 10.15 IBMQ Laboratory Profile.
  65. 10.16 IBMQ Jupyter Notebook Files view.
  66. 10.17 IBMQ Jupyter Notebook view.
  67. 10.18 From IBMQ’s Jupyter Notebook, the Qiskit version.
  68. 10.19 From IBMQ’s a code view from Jupyter Notebook.
  69. 10.20 VQE experiment with three qubits on linear and full entanglement
  70. 10.21 IBM ILOG CPLEX Optimisation Studio uses decision optimisation technology to create optimal plans, and schedules [157].
  71. 11.1 Quantum Optimisation in Qiskit. A high-level modelling language, a modular set of state-of-the-art quantum optimisation algorithms for different problem classes, leveraging Qiskit’s fundamental quantum algorithms as well as core circuit functionality; combined with a uniform and flexible interface for easy testing, benchmarking, and validation of models and algorithms [183].
  72. 11.2 Generated 10 Social Workers’ schedules
  73. 11.3 Generated 10 Social Workers’ Distance Matrix
  74. 11.4 Generated 10 Social Workers’ Distance Nodes
  75. 11.5 Outcomes from the SWP by the Backtracking algorithm. From Monday to Wednesday
  76. 11.6 Outcomes from the SWP by the Backtracking algorithm. From Thursday to Friday
  77. 11.7 Outcomes from the SWP by the Quantum Exact solver algorithm. From Monday to Wednesday
  78. 11.8 Outcomes from the SWP by the Quantum Exact solver algorithm. From Thursday to Friday
  79. 11.9 Outcomes from the SWP by the Quantum ASM Simulator from IBMQ. From Monday to Wednesday
  80. 11.10 Outcomes from the SWP by the Quantum ASM Simulator from IBMQ. From Thursday to Friday
  81. 11.11 Outcomes from the SWP by ibmq_16_melbourne v2.1.0 from IBMQ.
  82. 11.12 Outcomes from the SWP by ADMM optimiser from IBMQ.
  83. 11.13 Outcomes from the SWP by Minimum Eigen Optimiser from IBMQ.
  84. 11.14 Here we present the results by Monday of our algorithm. We compared the classical solver, the exact quantum solver, and the Variational Quantum Eigensolver. We can observe that the VQE, as an approximated algorithm, didn’t have time to find the best solution.
  85. 11.15 Here we present the results by Tuesday of our algorithm. We are comparing the classical solver and the exact quantum solver, and the Variational Quantum Eigensolver.
  86. 11.16 Here we present the results by Wednesday of our algorithm. We are comparing the classical solver and the exact quantum solver, and the Variational Quantum Eigensolver. We can observe that the VQE, as an approximated algorithm, didn’t have time to find the best solution.
  87. 11.17 Here we present the results by Thursday of our algorithm. We are comparing the classical solver and the exact quantum solver, and the Variational Quantum Eigensolver.
  88. 11.18 Here we present the results by Friday of our algorithm. We are comparing the classical solver and the exact quantum solver, and the Variational Quantum Eigensolver.
  89. 11.19 Here we present the results by analysing Friday of our algorithm. We are comparing the classical solver and the exact quantum solver, and the Variational Quantum Eigensolver.
  90. 11.20 The structure of the $ibmq\\_melbourne$ quantum device from IBM. This computer has fifteen superconducting qubits, which are connected by the $C_{NOT}$ gate. The bidirectionality of arrows reflects that each of the qubits can be both a control and a target.
  91. 11.21 Backtracking’s behaviour depending on the execution time and the number of patients.
  92. 11.22 VQE’s behaviour depending on the execution time and the number of patients and number of trials
  93. 11.23 SWP solved by OR-Tool-SAT from google
  94. 11.24 Results of the experimentation by comparing ten scenarios of the combinations of Social Workers’ schedules for a fixed patient’s location (for Monday). We plot the error bar of the median distribution of the location of each patient and their schedules concerning the number of repetitions of the quantum’s instance.
  95. 11.25 Results of the experimentation by comparing six scenarios of the combinations of Social Workers’ Problem on VQE and QAOA. By changing the number of patients, the social worker shot configuration intending to analyse the quantum cost to meet the optimal solution. We realise that the QAOA with the same settings as VQE finds the optimal solution with the little sample. We must indeed consider the high values of the shot parameter. The star is the medium and the red line real the result.
  96. 11.26 Results of the experimentation by hanging the number of patients, social worker shot configuration intending to analyse the quantum cost to meet the optimal solution. We realise that the QAOA with the same settings as VQE finds the optimal solution with the little sample.
  97. 11.27 The Standard Deviation expected total anneal time for 98$\%$ per cent success for each mapping value, with the best $\varepsilon$ for each shoot is shown. Our optimal case is for $\varepsilon=0,7$. Our most representative cases are for $\varepsilon=0,4$, $\varepsilon=0,7$ and $\varepsilon=1,1$.
  98. 11.28 Results of the experimentation by comparing ten scenarios of the combinations of Social Workers’ schedules for a fixed patient’s location. We plot the error bar of the median distribution of the location of each patient and their schedules concerning the number of repetitions of the quantum’s instance.
  99. 12.1 Case-Based Reasoning block diagram. For the standard CBR, two essential blocks are distinguished in this work. The classifier and the synthesiser. The classifier is made up of the retrieve and retain blocks and the re-use and revise blocks to make up the synthesis system.
  100. 12.2 VQE working principle based on the quantum variational circuit in Qiskit
  101. 12.3 VQE working principle based on the quantum variational circuit. Given an objective function that characterises the problem, with the help of the Ising Model block, we pass the objective function from the classical to the quantum domain. The ansatz is initialised with random values. Then, starting from these initial values (initial position) and depending on the measured value, a classical and external optimiser is used to feedback the new values of the ansatz parameters. So, until reaching the minimum energy value, equivalent to the ground state of our Hamiltonian, defined by the variational principle.
  102. 12.4 Quantum case-based system block diagram. In this scheme, to convert the classic CBR into quantum one, it is proposed to change the retrieve and retain blocks for a quantum variational classifier and the re-use and revise blocks for a synthesis system based on VQE with initial_point.
  103. 12.5 This is the variational classifier’s diagram block used in the qCBR, we use the data re-uploading technique to create an n-dimensional classifier as if it were a neural network where the non-linearity of the quantum gates will act as an activation function, and we will use the model $y=Wx+b$.
  104. 12.6 This is the design of the classifier implemented in qCBR. Considering that $x$ is the input data of dimension $l$, $Y_{c}$ is the label class of $x$, $k$ is the number of labels, and we use the fidelity cost (12.9). It is worth mentioning that the class of the tags $Y_{c}$ and, in this case, coincides with the computational base; thus, we save the target class. In this figure, we got $m$ layers.
  105. 12.7 Bloch sphere, where the infinite Hilbert vector space resides. It is worth remembering that Hilbert space is the immense place where the states that describe a quantum system live. Let N be the number of qubits and let $2^{N}$ be the space dimension. Given the 65-qubit IBM processor, it will be $3.68935×10^{19}$ dimensions. Many works of literature lead us to use or, at least, to think about using the quantum computer in Machine Learning (ML). By definition, the Hilbert vector space has defined these operations (internal and external products and mapping inputs in a large space) that a quantum computer performs natively and very easily [122].
  106. 12.8 $R_{y}$ and $R_{z}$ Ansatzes without entanglament used in qCBR experimentation.
  107. 12.9 $R_{y}$ and $R_{z}$ Ansatzes with $CRZ$ entanglement used in qCBR experimentation.
  108. 12.10 $R_{y}$ and $R_{z}$ Ansatzes with $CNOT$ entanglement used in qCBR.
  109. 12.11 Three-qubit quantum classifier circuit without entanglement.
  110. 12.12 Three-qubit quantum classifier circuit with entanglement by using $CZ$ or $CNOT$ gates
  111. 12.13 Representation of the generation of the $n$ weekly schedules of the SWP. The last plane, the one to the right of everything, represents all the SWP classes. The overlapping effect generated by the social workers’ problem’s characteristics and experimentation scenarios can be observed. This experimentation leads us to use the ICA technique to have a resulting dataset regardless of the schedules.
  112. 12.14 Fundamental processes to apply ICA to SWP dataset. The first thing that is done is to centre the data x by subtracting the mean, balancing the data x removing its variance, and calculating the unmixing matrix of W. Then, the new value of w is calculated. Then w is normalised before checking if, with the said value, the algorithm converges or not. If it does not converge, a new w must be recalculated, and if it converges, calculate the scalar product of $\langle x,y\rangle$ to obtain the independent weekly schedules.
  113. 12.15 qCBR’s Memory structure. The use the cross-validation technique helps to improve the quality of the classifier training[55]
  114. 12.16 Memory structure used for the Training System. A label identifies each class. And in this case, A is one of the labels. For more detail, refer to the code [Ade21].
  115. 12.17 The SWP is represented in vector form to take advantage of the Hilbert vector space’s characteristics within quantum computing. It is seen that each patient represents a dimension, and the points that make up the dataset are a dimension of $2n$ coordinates, $n$ being the total number of patients. In this figure, to simplify the understanding, we use two patients, therefore, two dimensions
  116. 12.18 Block diagram proposed for the resolution of qCBR, considering a real dataset with an overlap problem between the data components. This block diagram contemplates the treatment of the input data and the use of ICA [179] and PCA [222] before training and classifying the data. In this version, a classifier based on the re-uploader has been designed to handle the classification tasks. And for the synthesis tasks, a decision tree passed in the classifier predictions have been used together with the VQE plus the Initial_point
  117. 12.19 Comparative graphs between different ansatzes, taking into account the classifier’s accuracy as a function of depth. Represents the evolution of the ansatzes of dimension two and eight.
  118. 12.20 Energy comparison between VQE algorithm without using or using the initial point. It is noticeable how the first one tends to stabilise after multiple iterations (approximately 400), starting the search for a minimum from a random starting point (depending on the seed provided). Meanwhile, the second one is capable of stabilising and reach a solution close to the absolute minimum with much less iterations, starting from energy point evaluation close to the real energy solution
  119. 13.1 Distribution of considered order picking problems based on the percentage of publications.
  120. 13.2 Technical Specifications of the Quantum Hardware Technologies (Gate-based superconducting qubits, Gate-based ion traps and Quantum annealing) available in Amazon Braket.
  121. 13.3 Technical Specifications of Quantum Simulators systems where we can see it state vector simulator (34 qubits) and tensor network simulator (50 qubits).
  122. 13.4 We propose a robot that prepares batches and increases the efficiency of picking in a warehouse, taking advantage of the classic Machine Learning experience and leveraging hybrid computing (classical + quantum) in the cloud and distributed. This robot uses the Optimal routing strategy to calculate the shortest route, regardless of the layout or location of the items.
  123. 13.5 VQE working principle based on the quantum variational circuit.
  124. 13.6 Scenario 1, Independent lots. The robot receives the orders and calculates which order is the most optimal according to the coordinates in which each product is found. In this example, lot 4 is the most optimal.
  125. 13.7 Scenario 2, Collecting products in the same route from different batches. The robot will calculate a path that includes all the products to optimise their collection in a single journey. For example, if the product from Lot 2 is next to one from Lot 1, the robot will pick it up and store it in the basket from Lot 2.
  126. 13.8 Structure of our warehouse with pick locations. The warehouse has a rectangular layout with no unused space. We use all the parallel corridors. This proof of concept contemplates a single warehouse used to take the order and deliver it, and it is also divided into blocks, which contain slots for storing products, and transverse aisles separate them. The cross aisles do not have any products but allow the collector to navigate the warehouse. We base our picking strategy on minimising the route and optimising batch preparation. We do not contemplate shelving of different levels.
  127. 13.9 qRobot operation diagram. This diagram shows all the necessary blocks and processes that allow modelling the picking-batching problem and its proper functioning on the Raspberry Pi 4.
  128. 13.10 In these graphs, we can observe the results of the algorithm in different scenarios. A different colour represents each qRobots; qRobot number $1$ is red, next is blue, and the third is yellow, so on. While the depot is the $0$ node in yellow color and the rest of the nodes are represented in blue. The weights of each item (not normalised) in kg are $w_{0}=0,w_{1}=8,w_{2}=8,w_{3}=3$ and $w_{4}=3$. The maximum capacity of each qRobots is $45$. In this case, we have $4$ items and the possibility of using up to $3$ qRobots. Reading the images from left to right, we see that the nodes and their respective distances are shown in the first image. The second image shows the result of the algorithm having a qRobot. In the third and fourth images, we can see two different cases solved by two qRobots. And finally, in the fifth and sixth images, we can see two other issues solved by three qRobots. It is important to highlight that our algorithm in this proof of concept minimises the distance travelled and optimises the number of qRobots necessary to solve the cases presented. If it judges that the task can be performed with a single qRobot, it will not send $2$ qRobots.
  129. 13.11 In these graphs, we can observe the results of the algorithm in different scenarios. A different color represents each qRobots; qRobot number $1$ is red, the next is blue, the third is yellow, and so on, while the depot is the $0$ node in yellow color, and the rest of the nodes are represented in blue. The weights of each item (not normalised) in kg are $w_{0}=0,w_{1}=8,w_{2}=8,w_{3}=3,w_{4}=3,w_{5}=1,w_{6}=2$, and $w_{7}=4$. The maximum capacity of each qRobots is $45$. In this case, we have $7$ items and the possibility of using up to $4$ qRobots. Reading the images from left to right, we see that the nodes and their respective distances are shown in the first image. The second image shows the result of the algorithm having a qRobot. In the third and fourth images, we can see two different cases solved by two qRobots. And, finally, in the fifth and sixth images, we can see two other issues solved by three qRobots. It is important to highlight that our algorithm in this proof of concept minimises the distance travelled and optimises the number of qRobots necessary to solve the cases presented. If it judges that the task can be performed with a single qRobot, it will not send $2$ qRobots.
  130. 13.12 This figure shows that we judge important environments to carry out quantum computing to robotics and beyond. We can see the correct installation of TensorFlow 3.2.1 as required for all gradient operations; see the installation of Pennylane version 14.1, the installation of the latest version of Amazon Braket, and all the packages of the newest version of Qiskit 0.25 minus the qiskit-machine-learning package.
  131. 13.13 In this figure, we can see the correct installation of the Jupyter package and the Jupyter notebook that has been our environment of proof of concept. With this, everything is ready to import or write code in the different frameworks mentioned above (IMBQ, AWS-Braket, Pennylane and D-Wave).
  132. 13.14 This figure shows the files window through the CyberDuck client SSH [cyberd] viewer with the directory and file structure. And on the left, you can see the terminal that gives access to the qRobot. To access the qRobot by SSH, the username and password are required. Everything is configurable [config˙Rasp].
  133. 13.15
  134. 14.1 In this figure, we can observe a workflow of a quantum algorithm. First, let us remember that a quantum computer or hardware only executes a quantum circuit. But we can use classical algorithms to generate a description of our quantum circuit efficiently, so it would be smart to use it. Our quantum algorithm is born to execute or answer problems/approaches that are very expensive for classical computing. A good quantum algorithm would be the polynomial scale with qubits. This figure shows that we can clarify it polynomially given a problem and follow these guidelines.
  135. 14.2 We have installed the following frameworks successfully (Qiskit, Pennylane, AWS-Braket) on our Raspberry Pi 4 under the ARM64 operating system. More information about the qRobot platform can be found at Ref. [qRobot˙Platform˙lb]

###### List of Tables

  1. 4.1 In this table, we see the most used and known penalties. It is worth mentioning that binary variables satisfy $x_{i}^{2}=x_{i}.$
  2. 9.1 Comparation between Ising and QUBO representation and related terminology.
  3. 10.1 Weekly patient care schedules. It is not necessary to visit all registered patients every day of the week, as there can also be more than one patient assigned simultaneously on the same day. Where $U_{1}$ to $U_{2}$ are the patients (users) and equal to the variable $i$ or $j$ of the mathematical formulation
  4. 10.2 Status and release of the modules towards Qiskit 1.0
  5. 11.1 QUBO $Q$ Matrix for the Social Workers’ Problem
  6. 11.2 $J_{ij}$ Interaction forces between grid neighbours. We assume that $J_{ij}=0$ for $i$ and $j$ are not adjacent.
  7. 11.3 Calculated values of the external force $h_{i}$
  8. 11.4 This is $ibmq\\_16\\_melbourne\\_calibrations$
  9. 11.5 Experiment scenario using the Backtracking technique with 2, 3, 4 and 5 patients
  10. 11.6 VQE evolution of trials and number of patients
  11. 12.1 Table of the NN brute force’s, k-d tree’s, and Ball tree’s complexity method. Where $d$, is the data dimensionality, $N$ is the number of points in the training dataset and $K$ is the algorithm’s neighbours’ number
  12. 12.2 The result of the qCBR with a variational classifier and using the VQE and the Initial_point with some decision trees as a synthesiser (12.18). This table shows the different studies made as a function of the quantum circuit’s depth (layer). number of the patients and the social workers. The accuracy of the classifier is the maximum with the number of layers equal to 10. SW denotes Social Workers.
  13. 12.3 The result of the qCBR for a number of patients and social workers fixed at 5 and 4, respectively. The better behaviour of qCBR can be observed for some cases greater than 240. To have a good functioning of the qCBR, it must be iterated with the social workers’ dataset one 239 times. And at the case number of 240, we will have an accuracy of 92%. The ”accuracy” value is the percentage of the number of correct solutions found by the qCBR. A hyphen (-) denotes that no solution was found within the 20 cases. All these tests were done for the quantum circuit depth (layers) equal to 8.
  14. 12.4 The result of the qCBR for a number of patients and social workers fixed at 4 and 3, respectively. The better behaviour of qCBR can be observed for some cases greater than 240. To have a good functioning of the qCBR, it must be iterated with the social workers’ dataset one 239 times. And at the case number of 240, we will have an accuracy of 91%. The ”accuracy” value is the percentage of the number of correct solutions found by the qCBR. A hyphen (-) denotes that no solution was found within the 20 cases. All these tests were done for the quantum circuit depth (layers) equal to 8.
  15. 12.5 The classical CBR result on KNN classifier for a number of patients and social workers fixed at 5 and 4, respectively. The better behaviour of this CBR can be observed for some cases greater than 240. To have a good functioning of the CBR, it must be iterated with the social workers’ dataset one 239 times. And at the case number of 240, we will have an accuracy of 52.6%. The ”accuracy” value is the percentage of the number of correct solutions found by the CBR leveraged on KNN, applying a 10-KFold cross-validation process. A hyphen (-) denotes that no solution was found within the 20 cases. All these tests were done for the layer equal to 1.
  16. 12.6 The classical CBR result on KNN classifier for a number of patients and social workers fixed at 4 and 3, respectively. The better behaviour of this CBR can be observed for some cases greater than 100. To have a good functioning of the CBR, it must be iterated with the social workers’ dataset one 239 times. And at the case number of 240, we will have an accuracy of 70.3%. The ”accuracy” value is the percentage of the number of correct solutions found by the CBR leveraged on KNN, applying a 10-KFold cross-validation process. A hyphen (-) denotes that no solution was found within the 20 cases. All these tests were done for the layer equal to 1.
  17. 12.7 CBR with a neural network classifier and a backtracking algorithm as a synthesiser. SW denotes Social Workers.
  18. 12.8 CBR with a KNN classifier and a backtracking algorithm as a synthesiser. SW denotes Social Workers.
  19. 12.9 Table of the complexity of qCBR counting the PCA cases and the ICA complexity. In this case, K, the number of shots of the VQE, is fixed to 50.
  20. 13.1  In this experimentation, both the number of qRobots and their capacities (maximum load) are fixed and are worth $1$ and $45$ respectively. We compare the execution time of our algorithm in the different public access simulators in the market, solving the picking and batching problem. We see that for issues of this nature, and especially for the number of qubits required in each scenario, the behaviour of the D-Wave is the desired one at the temporal level, comparing it with technologies based on quantum gates. However, it should be noted that for the experiments on numbers of qubits less than $20$, the behaviour of these simulators is equated with the D-Wave. This experimentation helps to have a clear vision about the feasibility of this proof of concept.
  21. 13.2  Table of the computational results of our picking and batching algorithm on only $1$ qRobot. The value of time is an average and includes the waiting time, queue, execution and return of the solution. In the case of K is equal to $2$ for $9$ items with the qRobot capacity equal to $15$, the number of qubits is $188$. The execution time is on AWS Braket and on the D-Wave Advantage_system1 quantum computer. We can realise that there is a latency time in executing the algorithm from the qRobot to the real quantum computer. In the tests we’ve done, the quantum computer is in the US West (Oregon). Of all the tests that we have done, we have had an average latency time of about $2$ plus all the work management processes that rises more or less to about $8$ seconds. For the number of qubits exceeding 30, it is very convenient to use AWS-Braket (Advantage_system1.1)[221] instead of Qiskit or Pennylane. By the number of qubits and the execution time, that is differentially better. This scenario makes the use of quantum in robotics very viable. For the tests with a value of $M$ lower than those in the table, the number of qubits is relaxed, and the execution time is improved. This leads us to normalise the weights of the batches. Since the number of qubits follows the formula $K(n+1)(n+2)+K\lceil log_{2}M\rceil$.
  22. 13.3  In this table, we only consider the running time of the quantum algorithm on the real quantum computer from the qRobot (Advantage_system1.1 [221]), not counting latency time, job creation, and job return time.
  23. 14.1 PhD Tasks development

### Acronyms

##  Part I State of the Art

###  Chapter 1 Introduction

One of the most frequent problems in our daily lives is optimisation problems,
and for a long time, mathematics has always looked for a way to solve them.
The differential calculus technique helps solve these problems for certain
purposes that fulfil certain properties. However, many functions that appear
when trying to solve or model these tasks do not satisfy the hypotheses of the
differential calculus theorems, or have additional restrictions that nullify
their usefulness.

One of the successes of the last century in the field of mathematics was the
development of the simplex algorithm [79] for solving optimisation problems.
This success allowed us to find, and continues to allow us to find, the global
optimum of a linear function with linear constraints. However, some
limitations of this technique are observed when one wants to generalise the
algorithm or to solve more complicated problems that are not exclusively
summarised in finding the minimum of a linear function with linear
restrictions [78]. As a result, several numerical calculation tools were born
to approximate optimisation tasks under certain regularity conditions. Still,
they are not enough to try to solve all the problems. Most of the techniques
to solve these optimisation problems require continuity and differentiability
conditions. However, many of the functions that appear in these tasks to be
solved do not meet these conditions, and in some cases, it does not even make
sense to talk about these properties because we are dealing with a discrete
set. The field that deals with these last problems is known as combinatorial
optimisation.

The Travelling Salesman Problem (TSP) [145] belongs to this kind of problem
where the brute force algorithms, due to their computational impracticality
cost, grows factorially as a function of $N$, with $N$ being the number of
cities, making it difficult to have an efficient optimisation algorithm.

Due to this fact, there is then the need to develop specific algorithms for
each problem, making an in-depth study of this field and each of the available
techniques essential.

Some of these techniques are what are known as heuristic algorithms. The main
objective of these heuristic algorithms is to approach the global minimum of a
function, but without guaranteeing that it will be achieved. Instead, they
find a method of finding good solutions for a certain process (task). As we
discussed earlier, the same argument that prevents the impossibility of
finding global minimum search algorithms for any function makes it difficult
to choose the appropriate heuristic algorithm for each problem as well.
However, once again, the operation of this will depend on the nature of the
function with which we are working, making it necessary to adapt it.

Combinatorial optimisation problems, in which social workers visit their
patients in their respective homes and attend to them at a specific time,
called Social Workers’ Problem (SWP), are similar to TSP due to its NP-Hard
characteristic and require another focus if patient numbers grow considerably.
The problem of optimising the schedules of social workers who visit their
patients at home is a scheduling and routing problem of the NP-Hard class
[BOV94]. These difficulties will be observed with an increasing number of
patients where the number of possible solutions grows exponentially with the
size of the problem. The tasks subject to the labour of the social workers are
combinatorial optimisation problems and require an organisation based on time
and its execution. Moreover, because of the importance of these problems, we
usually find them in our daily life. These tasks may be subject to a finite
set of resources and restrictions due, for instance, to the physical
characteristics of the environment, temporary relationships, or the labour
regulations. In addition to conditions, the goal is to optimise one or more
criteria represented by an objective function that is usually related to cost,
benefit, or execution time.

The nature of the SWP invites us to analyse the main generalisations of the
TSP in search of a suitable formulation for our problem. To do this, we will
analyse some generalisations of TSP such as the Vehicle Routing Problem (VRP)
[73, 139, 208] and the Job Shop Scheduling Problem (JSSP) [50].

The generic VRP can be seen as the generalisation of the TSP, aiming to find a
set of routes at a minimal cost. Usually, the path is defined from the
beginning to the endpoint by passing through the depot to achieve the demand
of all nodes.

VRP is an NP-hard combinatorial optimisation problem that can be exactly
solved only for small cases of traditional computation problems. An approach
that allows better results in practice is the heuristic approach. However, it
does not guarantee optimisation. Thus, in recent decades, meta-heuristics have
emerged as the most hopeful research focus for the VRP family of problems.

Even with the best restrictions, the VRP (and without the scheduling
adaptation) continues to have exponential complexity depending on the growth
in the number of input data. This concept leads us to explore new approaches
to solve problems, such as large-scale social workers. Quantum computing [80]
could be one of these approaches.

Since Richard Feynman suggested that computing could be done more efficiently
by exploiting the power of quantum parallelism, [80, Har02], today, there is
evidence that makes quantum computing one of the most prominent candidates to
replace conventional silicon-based systems partially. During the last three
decades, one can find a series of quantum algorithms more efficient than the
better-known classical counterparts. The most renowned algorithms are the Shor
[201] and Grover [15, 47] algorithms. However, there is extensive literature
on quantum computing and techniques [170].

Today’s classical computers operate on individual bits, which store
information as binary 0 or 1 states. However, quantum computers use the
physical laws of quantum mechanics to manipulate data. The unit of information
is represented by a quantum bit or qubit at this fundamental level. Tangibly,
a qubit is any two-level quantum system. Mathematically, the state space of a
single qubit can be associated with the complex projective line over the
Hilbert space and satisfy that its euclidean norm is equal to one. A complex
quantum computing system is constructed by combining one-qubit systems.

There are two dominant techniques for quantum computing. Continuous-Time
Quantum Computing [129] used by D-Wave in which the problem to solve is mapped
in quantum hamiltonians (Hamiltonian is the energy representing function,
taking into account the energy of every possible configuration of the spins in
the ferromagnetic material.) and the natural dynamics of physical systems. The
Gate based Quantum Computing [158, Kir17] led by IBM, shows the computation
made through a series of discrete gate operations. While the following
reference [129] argues how Quantum Walk (QW), Quantum Annealing (QA), and
Adiabatic Quantum Computing (AQC) are related, we highlight that the QW and
AQC are pure quantum evolutions (unitary) as opposed to QA which involves
external cooling.

The Adiabatic Quantum Computing proposed by Farhi [Edw, 89], is based on the
adiabatic theorem [158]. This theorem affirms that if a quantum system is
driven by a progressively evolving Hamiltonian, which grows from one starting
point of the Hamiltonian ($H_{init}$) to the final point $H_{final}$, and
therefore, if the systems start in the ground state of $H_{init}$, the system
will finish up in the ground state of $H_{final}$. Adiabatic computing was the
first quantum computing technique [158].

Quantum Annealing, based on the adiabatic quantum computing paradigm, was
initially introduced by Kadowaki and Nishimori [124]. Since its proposal, the
QA technique has been a light for solving combinatorial optimisation problems.
This technique tries to solve problems similar to how optimisation problems
are solved using the classical simulated annealing [158]; from a multivariate
function formed from an energy landscape, the ground state corresponds to the
optimal solution of the problem. The most significant advantage of quantum
annealing is its high parallelism over classical code execution. It analyses
all possible inputs in parallel to find the optimal solution using quantum
tunnelling. This could be very useful when we want to reduce the complexity of
the NP-complete problems.

QA has confirmed its ability to solve a broad range of combinatorial
optimisation problems and also problems in other fields, such as quantum
chemistry (One of the fields that are taking great advantage of capacity and
the era in which quantum computing is right now) [158], bioinformatics[158]
and routing [139], to mention a few.

One of the widely used frameworks that helps to map our combinatorial
optimisation problem is Quadratic Binary Optimisation Problems (QUBO) [158,
124, 38].

QUBO, as NP-hard, refers to a pattern matching technique that, among other
applications, can be used in machine learning and optimisation, which involves
minimising a quadratic polynomial on binary variables[158]. QUBO has
demonstrated its potential in solving some standard combinatorial optimisation
problems such as the colouring of graphics, workshop planning, vehicle routing
and programming, neural networks, the partition problem, 3-SAT, and machine
learning where the parameters of the problem can be expressed as Boolean
variables [158, 124, 38]. As problems are constrained in real-life,
constraints can be mapped using the penalty function [151] taking advantage of
the Lagrange multiplier [49]. The QUBO formulation is suitable for annealing
architecture and has a connection with finding the ground state of the
generalised Ising Hamiltonian from statistical mechanics [151]. That means
QUBO can be mapped on the Ising model [158].

Advances in quantum computing offer a way forward for efficient solutions to
many cases of substantial eigenvalue problems unsolvable in a traditional way
[173]. Quantum approaches to finding eigenvalues previously relied on the
Quantum Phase Estimation (QPE) algorithm. The QPE is one of the essential
subroutines in quantum computation. It serves as a central building block for
many quantum algorithms and offers exponential acceleration compared to
classical methods, requiring several quantum operations
$O\left(\frac{1}{p}\right)$ to obtain an estimate with precision $p$ [173,
110].

Variational Quantum Eigensolver (VQE), proposed by Peruzzo [173] based on the
variational principle and form, estimates the ground state energy of the
Hamiltonian [83]. The VQE is a hybrid quantum/classical algorithm originally
proposed to approximate the ground state of a quantum system (the state
attaining the minimum energy). The VQE can be used to solve approximately the
optimisation problems.

Quantum Approximate Optimisation Algorithms (QAOA), based on the principles of
adiabatic quantum computation [158, 110, Qin18], is used to solve QUBO
problems. Farhi and Harrow showed the advantages of QAOA compared to classical
approaches [Edw, 89], while Rebentrost [187] just debated the problems of
constrained polynomial optimisation using adiabatic quantum computation
methods. Other scientists such as Vyskocil and Djidjev [214] worked on how to
apply restrictions in QUBO systems to avoid the use of large numbers of the
coefficients, thus resulting in more qubits from the use of quadratic
penalties, they proposed a new combinatorial design which involved solving
problems of linear programming of mixed integers to adapt applications
restitution. The following work [156] investigated and solved the Hamiltonian
cycle problem in computational frameworks such as quantum circuits, quantum
walks, and adiabatic quantum computing.

The methods mentioned earlier in quantum computing have been applied to
routing and scheduling techniques. For example, the Ref. [Seb19] contributed
an expansive vision and discussions on Ising formulations for various NP-
complete and NP-hard optimisation problems, emphasising using as few as
possible qubits. In the same way, there have been many works of literature on
the VRP and its variants.

The primary challenge is that existing quantum hardware does not yet seem
capable of running algorithms on large enough problem instances. Furthermore,
current quantum hardware is in the noisy intermediate-scale quantum (NISQ)
era, meaning that the present quantum devices are under-powered and suffer
from multiple issues.

Due to the quantum computing era, we are limited by the number of qubits and
thus, noise; we have to look for strategies and formulations that help us
solve real problems in this NISQ era.

We will take advantage of all these related works to define an appropriate
strategy for our thesis project in this NISQ era, going from the formulation
of the SWP, its implementation, experimentation, and the various comparisons
and the quantum machine learning approach to solve the SWP to its
generalisation with the qRobot.

####  1.1 Motivation

My primary motivation are social and technical. To design quantum algorithms
that can be executed in this NISQ era (reducing the number of the qubits) to
help African countries fight against extreme poverty and impact Western
companies and society on combinatorial optimisation problems, such as last
miles, location zone decision, routing, scheduling, picking and batching
issues, etc.

####  1.2 Work context

To develop this PhD thesis consisting of a theoretical and a practical part, I
have had to take some courses in the foundations of quantum physics. I have
had to develop and deepen optimisation mathematics, visit a quantum
laboratory, and work in the Boston ecosystem. I also needed to collaborate in
varied workgroups such as IBMQ, Xanadu, google, Quantum World, AWS Braket,
local groups such as Hispanic Computation, especially with the PhD Alberto
Enciso from advanced mathematics (CSIC). I have had to take some courses on
quantum computing work on the Qiskit textbook and Pennylane tutorial. In
addition, I have shared various results and research topics with the team led
by Steve Wood and Jan Rainer Lahmann (the CTO of Lufthansa and IBMQ) and work
with several different frameworks of payment, free, online and locally
(Qiskit, Pennylane, Cirq, Qibo, AWS_Braket, Raspberry Pi, etc.). I have
participated in various conferences, forums, hackathons and classes and have
advised on the writing of several quantum computing curricula. To finish, I
have met and collaborated with several renowned scientists of the different
computer techniques in marking and led collaborative projects and final
degrees at Valladolid and La Salle - Ramon Llull university on algorithms and
quantum approaches I designed within the framework of this thesis work.

####  1.3 Goals

This thesis aims to study art, and design a series of quantum algorithms on
combinatorial optimisation problems and implement them in this NISQ era. To do
this, we will define and create a combinatorial optimisation problem with
restrictions and solve it in two different approaches. Conversely, we will
formulate the problem mathematically in a top-down approach, both classically
and quantum. On the other hand, we will pose the problem statistically where
we will base its resolution on the machine learning technique of the base case
reasoning algorithm. Later, we will generalise our formulation of the SWP to
carry out efficient management of robots by substituting social workers for
robots and patients for pick-up orders (We call this generalisation qRobot).
Finally, we set another objective to design a collaborative didactic framework
for quantum university students with our DS4DS group.

In the path to attain its primary objective, this PhD research will also have
in mind the following goals:

  * $\diamond$

Updated state of the art concerning Combinatorial Problem, Linear and
Quadratic Constraints Solvers, Quantum Mechanic, Quantum Computers, Quantum
Gates, Quantum Circuits, Quantum Computing, and Quantum Machine Learning.

  * $\diamond$

State of the art of TSP, JSP and VRP.

  * $\diamond$

State of the art of heuristics for solving the combinatorial problems.

  * $\diamond$

State of the art of the concept of Hamiltonian of a system, Ising Hamiltonian
Model, The Hamiltonian of a TSP, the Hamiltonian of a JSP, the Hamiltonian of
a VRP.

  * $\diamond$

State of the art of the complexity class and Quantum Complexity class.

  * $\diamond$

Design and Model, mathematically the Social Workers’ Problem (SWP) as CSP
according to state of the art and the ones proposed in the scope of the PhD
work

  * $\diamond$

Study of the players involved in SWP, namely quantum computing frameworks,
quantum computers, and quantum research groups.

  * $\diamond$

Study and map the SWP in quantum computing.

  * $\diamond$

Developing and implementing the SWP in this NISQ era.

  * $\diamond$

Solve the SWP with QML. This methodology will be based on clustering and
classification techniques, resulting in a rule base concerning the SWP. An
extensive set of simulation results will be used as the basis for applying the
proposed QML method.

  * $\diamond$

Designing and implementing a quantum Case-Based Reasoning (qCBR).

  * $\diamond$

Designing and implementing a Quantum Enhanced Filter: QFilter.

  * $\diamond$

Designing and implementing qRobot: A Quantum computing approach in mobile
robot order picking and batching problem solver optimisation.

  * $\diamond$

Designing and implementing EVA: a quantum Exponential Value Approximation
algorithm.

  * $\diamond$

Testing and validating the developed models and approaches.

  * $\diamond$

Passing on the knowledge acquired to the group of DS4DS collaborators.

####  1.4 Hypothesis

In this era of quantum computing with few numbers of qubits, we know that
quantum optimisation algorithms based on the variational principle offer a
good approximation to the optimal solution, taking advantage of the
fundamentals of quantum mechanics such as superposition or quantum parallelism
plus interference, reducing in some cases the computing’s cost exponentially
compared to classical computing. However, due to this era’s technical
problems, NISQ (few useful qubits, decoherence and noise), we have to ask, to
what extent could we use quantum computing to solve an optimisation problem
with hard restrictions? Also, is it possible to solve quantum combinatorial
optimisation problems in Top-down’s philosophy and case-based reasoning?

####  1.5 Development of the thesis

This section will briefly present the technical results obtained in the
thesis. After reviewing state of the art research, techniques to solve
combinatorial optimisation problems, quantum fundamentals, current quantum
technologies, and the leading companies in these fields, we have focused on
defining combinatorial optimisation problems to respond to our thesis
hypotheses. First, we mathematically design and formulate the Social Workers
Problem (SWP) [22, 24, 23, 169, 20, Doc20, 64, 7, 5, 6] and define a heuristic
to allow this problem, which includes inequality and time constraints, to be
implemented in current quantum computers with very few qubits. To implement
this problem, we have had to analyse and study the Ansatzes and other various
variational algorithms such as VQE and QAOA.

Once the results were published at the 16th International Conference on Hybrid
Artificial Intelligence Systems (HAIS’21), we began to solve the same problem
(SWP) with the Machine Learning approach; we called this solution quantum
Case-Based Reasoning (qCBR) [26] inspired in classical Case-Based Reasoning.
The qCBR was plated as the sum of two large blocks (a variational classifier
and a synthesiser). The qCBR uses a data representation model from a
multidimensional vector in Hilbert space. It creates a vector subspace, where
each vector has the information that defines the SWP on the Hilbert vector
space and, when predicting whether an input vector (new case) corresponds to a
previously analysed class, the qCBR calculates the probability that each type
corresponds to the new vector from the proximity of each of the vector
subspaces generated from each category. The qCBR, with its synthesiser block,
refines the retrieved data in the case of not being the optimal result since
the qCBR has the function of ”generating” a new outcome based on the retrieved
information.

To scale the algorithms developed and to be able to compare them in various
technologies and quantum environments on the market (mainly Quantum Annealing
and Quantum Gate-Based computing), a problem was defined where SWP replaced
social workers with a mobile robot and had batches instead of patients. We
call the result qRobot: A Quantum computing approach in mobile robot order
picking and batching problem solver optimisation [25]. We developed a new
formulation, turned a Raspberry Pi 4 into a quantum ”computer,” and
implemented the solution. Finally, we studied the comparisons in AWS-Braket
(D-wave), Pennylane and Qiskit. The results were promising and the article was
published and on the cover of Algorithms magazine.

In parallel, we have been working to improve the VQE algorithm, the flagship
of quantum computing, and we published EVA: a quantum Exponential Value
Approximation algorithm [10]. We proposed a different way to VQE to calculate
the expected value given a quantum state. It should be remembered that the
largest cloud services platforms for quantum computers charge by the number of
shots and number of circuits. The VQE calculates the expected value by
decomposing the Hamiltonian into Pauli operators and obtains this value for
each of them, making simulations on cloud servers more expensive. After
completing our work, we designed an algorithm capable of calculating this
value using a single circuit. Finally, we carried out a cost-time study and
verified that it was possible to obtain a good performance in certain, more
complex Hamiltonians compared to current methods. Also, to consolidate our
vision of hybrid computing, we contributed a publication on CNNs with the
following article: Quantum Enhanced Filter, QFilter [21]. We proposed a hybrid
image classification model that took advantage of the potential of
convolutional networks in classical computing and replaced the classical
filters with variational quantum filters to reduce the computational cost of
classical computing. Similarly, this work would be compared with other
classification methods and system execution on different servers. It should be
remembered that convolutional filters are based on the scalar product and
represent a high cost for classical computation. In contrast, this operation
(scalar product) is native to quantum computation (Hilbert vector space).

The feasibility of all the algorithms that we have proposed has been made in
various environments such as Qiskit, AWS-Braket, D-Wave, Pennylane and Qibo.

####  1.6 Thesis structure

This thesis is organised as follows. In section (2), we review the
Optimisation combinatorial problems related to our topic. Chapter (3), we
introduce the systems and useful concepts needed for the methods to solve the
optimisation problems. In section (4), we present the methods to solve
combinatorial optimisation problems. The Quantum Mechanic is introduced in
chapter (5), reviewing the quantum mechanics postulates. We introduce the
Complexity Class in section (6). After analysing the quantum complexity in
chapter (7), we revise the useful quantum gates. Quantum computers and the
players are the subjecta of chapter (8). Chapter (9), we delve deeply into the
most important technics in quantum computing. In section (10), we develop the
research design and analyse our experiment tools, the quantum frameworks, and
some experiments over quantum algorithms and technics. Section (11), we
present our approaches to solving the Social Workers’ Problem. Section (12) we
present a quantum machine learning approach to solve the SWP. In section (13)
we generalise the SWP as qRobot. Section (14) and (14.2), we show the results
and emphases on a discussion over these results, and in our final chapter, we
conclude and offer the potential for further work.

###  Chapter 2 Combinatorial Optimisation problems

####  2.1 Introduction

Combinatorial optimisation means searching for an optimal solution in a finite
or infinite set of potential solutions. Optimality is defined concerning some
criterion function, which must be minimised or maximised is usually called the
Cost function or Objective function.

The Social Workers’ Problem can be seen as the combination of a scheduling and
routing problem. Because of this, we will explore some scheduling and routing
algorithms. The first study will be the Travelling Salesman Problem (TSP)
algorithm but with the mind of adding some time variables and redefining the
variables to be optimised.

####  2.2 Travelling Salesman Problem

The Travelling Salesman Problem known as TSP is defined as follows: Given a
list of cities and the distances between each pair of cities, what is the
shortest possible route that visits each city exactly once and returns to the
origin city?

We label the cities by an integer $\\{1,...,N\\}$ according to their list
order. We denote by $d_{ij}$ the distance between cities $i$ and $j$. We can
associate each possible solution $p$ of the problem to a permutation
$(x_{1},...,x_{N})$ that affects the order in which they are going to be tour
the cities, and taking as function
$f(p)=d_{x_{1},x_{2}}+...+d_{x_{N-1},x_{N}}+d_{{x_{N}},x_{1}}$, where
$d_{x_{i},x_{i+1}}$ corresponds to the distance between the cities $x_{i}$ and
$x_{i+1}$, we have that our goal will be to find the minimum of $f$ in the set
of permutations.

TSP is an NP-Hard problem within combinatorial optimisation. The problem was
first formulated in 1930, and it is one of the most studied optimisation
problems. Although the situation is computationally complex, many exact
heuristics and methods are found to solve some instances from one hundred to
thousands of cities.

In the TSP formulation (2.1) to (2.5), in this case, the distance matrix of
the TSP will be determined by the elements $d_{ij}$ indicating the distance
(cost) between node $i$ and node $j$. The decision variables are $x_{ij}=1$,
if the solution to the TSP goes from city $i$ to city $j$, $x_{ij}=0$,
otherwise. Then the solution of the problem is found by solving the
formulation. This formulation is known as MTZ [161].

$\text{min}\sum_{i=1}^{N}\sum_{j=1}^{N}d_{ij}x_{ij},$ (2.1)

$\sum_{i=1}^{N}x_{ij}=1\quad\forall j\in\\{1,...,N\\},\\\ $ (2.2)

$\sum_{j=1}^{N}x_{ij}=1\quad\forall i\in\\{1,...,N\\},\\\ $ (2.3)

$\displaystyle x_{i,j}\in\\{0,1\\}\quad\forall i\in\\{0,\ldots,N\\},$ (2.4)
$\displaystyle\quad\forall j\in\\{0,...,N\\},$

$u_{i}-u_{j}+Nx_{i,j}\leq N-1\quad 1\leq i\neq j\leq N.$ (2.5)

In this formulation, the objective function equation (2.1) minimises the cost
function. The restrictions equations (2.2) and (2.3) declare that each
salesman can only be in one node at any time. The restriction (2.4) describes
that $x_{ij}$, are binary variables. The constraint (2.5) are the route of
continuity and the elimination of sub-courses, which ensure that the solution
does not contain a sub-route disconnected from the exchange.

There are $N!$ possible routes (for the exact calculation). However, it can be
simplified since the starting point does not matter; we can reduce the number
of routes examined by a factor $N$, leaving $(N-1)!$ possible solutions. Also,
if the direction in which the traveller is travelling does not matter, the
number of routes to be examined is again reduced by a factor of $2$.
Therefore, the number of the possible paths is $\frac{(N-1)!}{2}$.

#####  2.2.1 Constructive heuristics

Following our analysis, we understand by a heuristic method, an approach to
problem-solving that uses a practical technic or various shortcuts to produce
solutions that may not be optimal but are sufficient given a limited
timeframe.

We find that the constructive heuristics are based on the Nearest Neighbour
algorithm (NN) [62] or also called Greedy algorithm [62], which allows the
traveller to choose the nearest unvisited city as the next move. This
algorithm quickly returns a lower-cost route. For $N$ cities randomly
distributed on a plane, the algorithm on average returns a path 25$\%$ longer
than the smallest path possible. However, in many cases, they exist where the
distribution of the given cities makes the NN algorithm return the worst path
[112]. This occurs for both symmetric and asymmetric TSPs [113]. Rosenkrantz
showed that the NN algorithm has an approximation factor of order $O(logN)$
for instances that satisfy the triangular inequality; with $N$ the number of
the cities. A variation of the NN algorithm, called Nearest Fragment operator,
is the one that connects a group of closest unvisited cities and can find the
shortest route with successive iterations. The NF operator can also be applied
to obtain initial solutions for the NN algorithm and be improved in an elitist
model where only the best solutions are accepted. There are other heuristic
techniques in Local Search Algorithms [123], but we will not address them
classically in this thesis.

Another formulation approach is the Job Shop Scheduling Problem (JSSP) that we
will analyse in the following section.

####  2.3 Job Shop Scheduling Problems

The Job Shop Scheduling problem [56, 57, 42, 65], known as JSSP, consists of
planning a set of $N$ jobs $\\{J_{1}\text{, ...,}J_{N}\\}$ on a set of $M$
resources or physical machines $\\{R_{1}\text{, ...,}R_{M}\\}$. Each $J_{i}$
job consists of a set of visits or operations $\\{V_{i1}\text{, . . . ,
}V_{iM}\\}$ that have to be executed sequentially. Each $V_{il}$ visit has a
runtime of $p_{V_{il}}$ of time during which it requires the exclusive use of
a single resource,$V_{il}$, starting from start time $st_{V_{il}}$ to be
determined.

Each job has an earlier start time and is sometimes considered a later end
time, forcing visit start times to take values in finite domains.

The $JSSP$ has three restrictions: sequential or precedence restrictions,
capacity restrictions and non-expulsion restrictions of the machines.
Sequential constraints are defined by the sequence of visits to a job and can
be described by linear inequalities of the type: $st_{V_{il}}+p_{V_{il}}\leq
st_{V_{i\left(l+1\right)}}$ that is, the visit $V_{il}$ must be carried out
before the visit $V_{i(l+1)}$. The capacity constraints restrict the use of
each resource to a single visit at each instant of time and can be described
as a disjunctive constraint of the form: $st_{v}+p_{v}\leq st_{w}$ or
$st_{w}+p_{w}\leq st_{v}$ if $R_{v}=R_{w}$. This last constraint means that
two tasks that use the same resource cannot overlap. Lastly, the non-expulsion
restrictions express that once the start time has been determined,
$st_{V_{il}}$ for a visit $V_{il}$, this visit must be carried out during the
time interval $[st_{V_{il}},st_{V_{il}}+p_{V_{il}}]$ without interruption.

The objective is to find optimal planning for a specific criterion, the most
common being the following three:

  * $\diamond$

Makespan is the end time of the last visit, and time is denoted as $C_{\max}$.
This version of the problem is known, in the literature, as $J||~{}C_{\max}$
[56, 57].

  * $\diamond$

Total Flow is the sum of the end times of all the works. This version is known
as $J||\sum C_{i}$, with $C_{i}$ is the time of completion of the work $J_{i}$
[56, 57].

  * $\diamond$

Tardiness is a delay time of the works. This version is known as $J||\sum
T_{i}$ with $T_{i}$ as the tardiness, $T_{i}=\text{max}\\{0,C_{i}-d_{i}\\}$
with $d_{i}$ is the due date of the visit $i$ [56, 57].

Regarding the analogy, in our case, the $N$ jobs $\\{A_{1},...,A_{N}\\}$ will
be the assistants and the physical machines $\\{P_{1},...,P_{M}\\}$ will be
patients. So from here, the same description and variables are respected.

We can consider a $JSSP$ as a $TSP$ executed $M$ times or see it another way
as the TSP is a particularisation of the JSSP taking into account $N$ jobs on
a single machine. Being the travelling salesman, the machine and the works the
cities.

Another approach to solving the problem is to use a generalisation of the TSP.
In this case, the VRP.

####  2.4 Vehicle Routing Problem

The Vehicle Routing Problem known as VRP which asks What is the optimal set of
routes for a fleet of vehicles to traverse in order to deliver to a given
group of customers?

In VRP, the goal is to find optimal routes for multiple vehicles visiting a
set of locations. (When there is only one vehicle, it is reduced to TSP). What
do we understand by optimal routes for a VRP? In the context of this thesis,
the answer is the same as for a TSP; routes with the shortest total distance.

Since the study focuses on an optimisation problem, a good definition for
optimal routes would be to minimise the most extended single path among all
vehicles. This is the correct and best-known definition if the goal is to
complete all deliveries as soon as possible.

It is essential to see that the basis of this formulation is TSP. So, we can
find a general formulation on the TSP that includes restrictions such as:

  * $\diamond$

Maximum travelled distance restrictions.

  * $\diamond$

Visit time.

Let $G=\left(V,E\right)$ be a complete directed graph with
$V=\\{0,1,2,..,N\\},$ as the set of nodes and $E=\\{\left(i,j\right):i,j\in
V,i\neq j\\}$ as the set of arcs, where node 0 represents the central, for the
$K$ vehicles with the same maximum travelled distance $q$ and $N$ remaining
nodes that represent geographically dispersed cities/locations. In this case,
the distance matrix of the VRP will be determined by the elements $d_{ij}$
indicating the distance (cost) between node $i$ and node $j$. The VRP
formulation is described as follow:

$\text{min}\sum_{i=1}^{N}\sum_{j=1}^{N}d_{ij}x_{ij},$ (2.6)

$\sum_{i=1}^{N}x_{ij}=1\quad\forall j\in\\{1,...,N\\},\\\ $ (2.7)

$\sum_{j=1}^{N}x_{ij}=1\quad\forall i\in\\{1,...,N\\},\\\ $ (2.8)

$\small\small\sum_{j=1}^{N}x_{0j}=K~{}~{}~{}\forall i\in 1,\ldots,N,$ (2.9)

$\small\small\sum_{j=1}^{N}x_{j0~{}}=K,~{}~{}~{}\forall i\in 1,\ldots,N,$
(2.10)

$\small\small\sum_{i=1}^{N}\sum_{j=1}^{N}x_{ij}d_{ij}\leq q,$ (2.11)

$u_{i}-u_{j}+Nx_{i,j}\leq N-1\quad 1\leq i\neq j\leq N,$ (2.12)

$\displaystyle x_{i,j}\in\\{0,1\\}\quad\forall i\in\\{0,\ldots,N\\}$ (2.13)
$\displaystyle\quad\forall j\in\\{0,...,N\\}.$

In this formulation, the objective function equation (2.6) minimises the cost
function. The restrictions equations (2.7) and (2.8) declare that each vehicle
can only be one node at any time. The constraint (2.9) establishes that all
the vehicles start from Depot and (2.10) establishes that all the vehicles end
at the Depot. The restriction (2.11) establishes that any vehicle can’t travel
more distance than allowed. In the case of wanting to measure the time, here,
what we would do is change the matrix $d_{ij}$ for a matrix of the maximum
contract time. The constraints (2.12) are the route of continuity and the
elimination of sub-courses, which ensure that the solution does not contain a
sub-route disconnected from the exchange. Restrictions (2.13) describes that
$x_{ij}$, are binary variables.

It is also observed that the Vehicle Routing Problem can serve to encode the
difficulty of finding the optimal schedules of the $N$ social assistants
(vehicles) who visit the $m$ patients (locations).

Up to this point, the mathematical formulation of equations (2.6) to (2.13)
represents a conventional CVRP. To solve a scheduling problem, we will need a
time variable. The introduction of time (schedule) into the QUBO formulations
of the CVRP is a significant obstacle to formulating several important VRP
restrictions associated with the Vehicle Routing Problem with Time Windows
(VRPTW) [168].

During the state of the art of these formulations carried out, we have found
several articles [168, 90, 117] that solve the TSP and VRP for annealing
computers [53, 45, 76]. However, the number of variables is still intractable
for the current size of quantum computers. The number of qubits of the TSPTW
[168], is proportional to $N^{3}+N^{2}\log_{2}N$, and for this VRPTW [117], is
$N^{4}$. For this reason, we will propose a new VRPTW formulation ((11.9) and
(11.10)) with a heuristic function executed by an classical algorithm that
generates a description of a quantum circuit as advocate the following
reference [96]. With this strategy, we aim to reduce the number of the qubits
from $N^{4}$ to $N^{2}$ for our proposed VRPTW for solving our SWP.

The new formulation of the VRPTW will be developed in section (11).

####  2.5 Summary

In this section, we have introduced some classical combinatorial algorithms on
which we will base the design of our SWP. We have reviewed state of the art,
both the definition and the formulations of the $TSP$ with its techniques of
constructive heuristics. We also analysed the $JSSP$, which despite being an
algorithm designed for factories, can be used to model the SWP and finally,
the VRP. We have also realised that since we want to implement this SWP with
the VRPTW, we will need to define a strategy since the number of qubits of the
VRPTW is proportional to $N^{4}$, making it intractable to implement today in
a gate-based quantum computers.

To summarise, we observed that even with the best restrictions, heuristics or
programming techniques, depending on the size of the data considerably high,
the best $TSP$, $JSSP$ or $VRP$ requires a very high computational cost for
classical computing and would continue to approach an exponential cost.

In these cases of exponential computational cost, another approach would be
needed, such as using the power of quantum computing to solve the problem of
this magnitude.

Now we have to relate these classical algorithms with the usual concepts that
can be of great help in the development of this thesis.

###  Chapter 3 Systems and useful concepts

####  3.1 Introduction

This chapter will work on concepts and systems we need to solve combinatorial
optimisation systems based on graph. We will also analyse some necessary
concepts that relate the resolution of the Ising model with graph theory and
the basic Hamiltonian path of solving a routing problem such as SWP.

A Hamiltonian system is a dynamic system, that is, a system whose state
evolves with time, governed by Hamilton’s equations. These systems are
essential in dynamic optimisation techniques [Ant10].

Next, we will analyse the Hamiltonian path, Hamiltonian cycles, and the Ising
model.

####  3.2 Hamiltonian path and cycles

Let $G=(V,E)$, and $N=|V|$ be the graph and the Rank respectively. Having the
following vertices $\\{1,...,N\\}$, and the set of edges $(uv)$ to be directed
(the order $(uv)$ matters), it is trivial to extend to non-directed graphs,
just considering a directed graph with $(vu)$ added to the set of arcs each
time $(uv)$ is added to the arc set.

A Hamiltonian path, in the mathematical field of graph theory, is a graph
(Figure (3.1)) path between two vertices of a graph that visits each vertex
exactly once. When the last vertex visited is adjacent to the first, the path
is a Hamiltonian cycle.

Figure 3.1: Shows a graph of 26 vertices in which a Hamiltonian cycle is
highlighted

A Hamiltonian cycle is defined as a closed-loop, graph cycle on a graph where
every node (vertex) is visited exactly once.

A loop is just an edge that connects a node to itself; a Hamiltonian cycle is
a path travelling from a point back to itself, visiting every node en route.

In the next paragraph, we will analyse the Ising model and its relationship
with solving optimisation problems.

####  3.3 Ising model and the Hamiltonian

The Ising model is defined as a mathematical model of ferromagnetism in
statistical mechanics. The model consists of discrete variables representing
magnetic dipole moments of atomic ”spins” in one of two states $+1$ and $-1$.

Unfortunately, solving the spin system is costly because the energy landscape
is equivalent to finding the global minimum of a function with several local
minima. Thus, the Ising model describes the system’s energy, and the operator
or equation that describes the system is known as the Hamiltonian (see
equation (3.1)).

Finding the lowest energy of the spin system is equivalent to finding its best
configuration (the global minimum of the associated function).

This problem is somewhat equivalent to a QUBO, which we will develop deeply in
section (9). The only difference is that the QUBO works with binary variables
and the Ising model with variables between $-1$ and $1$. Thus, we can
summarise that the correspondence between a computer problem (QUBO) and a
physical system is a change of a variable.

A Hamiltonian ($H$) is the function that represents the energy of the every
single possible configuration of the spins in the ferromagnetic material.

$H=-\sum_{\langle
i,j\rangle}J_{ij}\sigma_{i}\sigma_{j}+\sum_{i}{}h_{i}\sigma_{i}.$ (3.1)

Where $J_{ij}$ represents the spin-spin interaction, $h_{i}$ represents the
external field, and $\sigma_{i}$, $\sigma_{j}$ are the individual spins at
each lattice site. The first sum is over all pairs of neighbouring lattice
sites (also known as links); it represents the interactions between spins. The
second sum is over all the lattice sites themselves; denotes the external
field trying to align all spins in one direction. It is worth mentioning that,
in the Ising model, each lattice site (figures (3.2) and (3.3)) only interacts
with the sites directly adjacent to it on the lattice; why the notation
$\langle i,j\rangle$.

On one hand, the size of $h_{i}$ represents how strong the field is, so it
tells us how much higher in energy one spin is than the other. Its sign tells
us whether it’s spin up or spin down that’s preferred. On the other hand, the
size of $J_{ij}$ tells us how strongly neighbouring spins are coupled to each
other; That means how much they want to (anti-)align. Physically, the strength
of spin-spin coupling could depend on the distance between them in the
magnet’s lattice, for instance. So its sign tells us whether neighbours prefer
to align or anti-align. Physically, whether material is one or the other (or
neither) depends on the exact quantum mechanical details of how the spins
interact.

Figure 3.2: A Lattice in the Euclidean plane [LatticeGraph] Figure 3.3: Five
Lattices in the Euclidean plane [LatticeGraph]

Spin glasses are systems of $N$ particles in which each particle can take two
values: $-1$ and $+1$. The set of all possible values of the $N$ particles is
called the configuration space and is designated as $\\{+1,-1\\}^{N}$.

The work of many researchers, mathematical, physical and electronic, has
facilitated the conclusion that spin glasses can be used to model quantum
states. The contribution of Manuel de la Rosa Fernández[190] reaches the same
conclusion.

There are constructions known as ”p-spin lenses”, which often lead to
interactions of three bodies or more in $H$, and which can later be used to
reduce the problem to an Ising spin glass, introducing a polynomial number of
turns that help reinforce the interaction of three bodies through multiple
interactions of two bodies $s_{1}s_{2}$ [28] [41].

Based on Andrew Lucas’s work[151], the author concludes that almost all famous
$NP$ [97] [127] problems can be written as Ising models with a polynomial spin
number that does not scale faster than $N^{3}$. This work is essential for
writing any quantum optimisation algorithm.

####  3.4 Summary

In this section, we have reviewed the state of the art of useful concepts to
develop this thesis. We have introduced the Ising model and the Hamiltonian as
the energy function.

All these concepts, theories and analyses are important to solve combinatorial
optimisation systems, and they will help us fully when it comes to modelling
our problem. In our case, we will further develop each constraint that we will
map into the objective function. For all this, in the next section, we will
analyse combinatorial optimisation problems and their resolution.

###  Chapter 4 Solving combinatorial optimisation problems

####  4.1 Introduction

This chapter will review existing methods for solving constrained optimisation
problems. For this, we need to analyse the existing programming techniques and
improve them in the face of our mission.

####  4.2 Linear Programming

Almost all the approximation algorithms that we know are built based on Linear
Programming (LP).

Linear Programming is defined as the problem of optimising (minimising or
maximising) a linear function subject to linear inequality constraints. The
function being optimised is called the objective function.

Linear Programming corresponds to an algorithm through which real situations
are solved. It aims to identify and solve difficulties to increase
productivity concerning resources (mainly limited and expensive), thus
increasing benefits.

How to solve a problem using LP?

The first step in solving a linear programming problem is to identify the
essential elements of a mathematical model; these are:

  * $\diamond$

Objective Function

  * $\diamond$

Variables

  * $\diamond$

restrictions

The next step is to determine the following goals, for which we propose to
follow the following methodology.

  1. 1.

Define the objective function criteria

  2. 2.

Identify and define variables

  3. 3.

Identify and define constraints

  4. 4.

Present the Objective Function

#####  4.2.1 The Objective function, decision variables and the constraints

The objective function is directly related to the general question that one
wishes to answer. If different questions arise in a model, the objective
function would be associated with the higher-level question, the fundamental
question.

The decision variables are identified, starting from a series of questions
derived from the fundamental question. Decision variables are the controllable
factors of the system that one is modelling. They can take various possible
values, of which it is necessary to know their optimal weight, contributing to
the achievement of the objective of the general function of the problem.

When we talk about constraints in a linear programming problem, we are
referring to everything that limits the freedom of the values that decision
variables can take. The constraints of the problem determine the conditions in
which the use of resources is feasible, taking into account all the tasks of
the problem.

The best way to find them is by thinking about a hypothetical case that was
decided to give infinite value to the decision variables. For example, in the
case of a TSP, one restriction will be to visit the city only once.

In the case of the allocation algorithm, the decision variables $x_{ij}$ are
incorporated, which are binary variables that take the value $x_{ij}=1$ as
long as $b_{i}$ is assigned to $a_{j}$ and that $x_{ij}=0$. If these options
were not given, the following restrictions (4.1) and (4.2) would be
established:

$\sum_{i=0~{}i\neq j}^{N}x_{ij}=1,$ (4.1) $\sum_{j=0~{}i\neq
j}^{N}a_{ij}x_{ij}\leq b_{i}.$ (4.2)

Where $a$ is a matrix and $b$ is a vector. The first restriction, equation
(4.1), means that visits will be made only by an agent. While the second
restriction, equation (4.2), means that the set of visits made by an agent
will not exceed the limit of resources that the agent has available. In the
case of an exact TSP, the first set of equalities ensures that each exit city
$\\{0,...,N\\}$ reaches exactly one city. The second set of equalities
provides that from each city $\\{1,...,N\\}$ exit exactly into a town (both
restrictions also imply that there is precisely one exit from town 0).

For a positive scalar $P$ (Lagrange Multiplier) and $y_{i}$ as the ancillary
variables. Equations (4.3) and (4.4) are the penalty functions corresponding
to constraints (4.1) and (4.2).

$P(\sum_{i=0~{}i\neq j}^{N}x_{ij}-1)^{2},$ (4.3)

$P(\sum_{j=0~{}i\neq j}^{N}a_{ij}x_{ij}-b+\sum_{i=0}^{\lceil
log_{2}b\rceil}2^{i}y_{i})^{2}.$ (4.4)

#####  4.2.2 Formulation of linear programming of binary integers

Let us introduce a linear programming of binary integers as follows: If
$z_{1},z_{2},z_{3},\ldots,z_{N}$ are $N$ binary variables, which are ordered
in a vector $z$, what is the most substantial value of $c\cdot z$, for some
vector $c$, given a constraint?

$Sz=b.$ (4.5)

From (4.5) with $S$ an $m\times N$ matrix and $b$ a vector with $m$
components, it is known that the resolution of this equation has an NP-hard
complexity, with a corresponding NP-complete decision problem. As discussed
above, almost most daily challenges are combinatorial optimisation problems,
and in many cases, the framework use to model these problems is the ILP [194].
In our case, a social worker must maximise visits to a home patient, given the
regulatory restrictions of her/his contract.

Let $H=H_{A}+H_{B}$ be the Hamiltonian (mathematical and physical model
introduced above) defined by (4.6).

$H_{A}=A\sum_{j=1}^{m}\left[b_{j}-\sum_{i=1}^{N}S_{ji}z_{i}\right]^{2}.$ (4.6)

With $A\in R^{+}$. The ground states of $H_{A}=0$ enforce the constraint that
$Sz=b$. Then you get that

$H_{B}=-B\sum_{i=1}^{N}c_{i}z_{i}.$ (4.7)

With $A\gg B$ and $B$ is a positive constant.

To find restrictions on the required $A/B$ ratio, Let us proceed as follow. It
is assumed that the constraint of the equation $Sz=b$ can be satisfied with a
selection of $z$. Taking this in account, the most meaningful possible value
of $-\Delta H_{B}=BC$ is shown as the constraint limits where:

$C=\sum_{i=1}^{N}\text{max}(c_{i},0).$ (4.8)

One way of adjusting the Lagrange multiplier is given as described as the
following. The lowest value of $\Delta H_{A}$ is leveraged on the properties
of the matrix $S$ and would occur if only a single constraint were violated.
That constraint was broken by the least amount possible, given by (4.9).

$S\equiv\mathop{{\mathop{\min}}}_{\mathop{\sigma}_{i}\in\\{0,1\\},j}\left(\max\left[1,\frac{1}{2}\sum_{i}\left(-1\right)^{\sigma_{i}}S_{ji}\right]\right).$
(4.9)

This limit could be improved if more specific properties of $S$ and $b$ are
known.

It can be concluded that if the coefficients $c_{i}$ and $S_{ji}$ are
integers, we have that $C\leq N$ max($c_{i}$) and $S\geq 1$, so it is
concluded that $A/B\geq N$.

####  4.3 Quadratic Programming

The Quadratic programming can be stated as the procedure that minimises a
quadratic function of $n$ variables subject to $m$ linear constraints of
equality or inequality.

A quadratic program is the simplest nonlinear problem with inequality
constraints. Quadratic programming is important because many issues appear
naturally as quadratic (least-squares optimisation, with linear constraints).
Besides, it is important because it appears as a sub-problem frequently to
solve problems, not more complicated linear. The techniques proposed to solve
quadratic issues have a lot in common with linear programming.

Specifically, each inequality must be satisfied as equality. The problem is
then reduced to a search for vertices precisely as it was done in linear
programming, where $c$ is a vector of constant coefficients; $A$ is a matrix
$(m\times n)$, and it is generally assumed that $Q$ is a symmetric matrix.
Since the constraints are linear and presumably independent, the qualification
of the restrictions is always satisfied, so the Karush-Kuhn Tucker conditions
are also sufficient conditions to obtain an extreme that will also be a global
minimum if $Q$ is positively defined. On the other hand, if $Q$ is not defined
as positive, the problem could be unbounded or lead to local minima. Quadratic
Programming plays a significant role in linear and nonlinear optimisation
theory since it is closely related to LP and is an essential intermediate step
to effectively solving general Nonlinear Programming problems. In the case of
solving the Hamiltonian of the Ising model, the two instances of solving the
quadratic minimisation problems will be seen.

#####  4.3.1 Quadratic Formulation

Let ${f:}\mathbb{R}^{n}\rightarrow\mathbb{R}$, $f$ be a quadratic function if:

$f\left(x_{1},~{}x_{2}\text{, . . . ,
}x_{n}\right)=\sum_{i,j=1}^{n}q_{ij}x_{i}x_{j}=\left(x_{1},~{}x_{2}\text{, . .
. , }x_{n}\right)\left(\begin{matrix}q_{1,1}&\cdots&q_{1,n}\\\
\vdots&\ddots&\vdots\\\ q_{n,1}&\cdots&q_{n,n}\\\
\end{matrix}\right)\left(\begin{array}[]{c}{x_{1}}\\\ \vdots\\\ {x_{n}}\\\
\end{array}\right).$ (4.10)

Let us focus on one of the properties of the quadratic function as follows:

$f\left(\lambda x_{1},~{}\lambda x_{2}\text{, \ldots, }\lambda
x_{n}\right)=\lambda^{2}f\left(x_{1},~{}x_{2}\text{, \ldots, }x_{n}\right).$
(4.11)

On the one hand, Quadratic Minimisation Problems subject to equality
constraints require minimising the objective function $f\left(x\right)$
subject to linear equality constraints $Ax=b$.

But when these are subject to linear inequality constraints, they require
minimising the objective function $f(x)$ subject to these constraints $Ax=b$,
and may even contain equality constraints.

$\text{min}f(x)=\frac{1}{2}x^{T}Qx+c^{T}x.$ (4.12)

Subject to:

$Ax\leq b,$ (4.13) $x\geq 0.$ (4.14)

Where $c$ $\in R^{n}$ is a row vector, $x$ $\in R^{n}$ and $b$ $\in R^{n}$ are
column vectors. Let consider also that $Q=q_{ij}$ $\in M_{n\times n}$ and
$A=(a_{ij})\in M_{n\times n}$ are matrices and the superscript $T$ denotes the
transpose. The elements $q_{ij}$ of $Q$ are constants given such that
$q_{ij}=q_{ji}$ (that is, $Q$ is a symmetric matrix, $Q^{T}=Q$. Thus, the
objective function is expressed in terms of these $q_{ij}$, the elements
$c_{j}$ of $c$ and the variables $x_{j}$, as follows:

$f(x)=\frac{1}{2}x^{T}Qx+c^{T}x=\sum_{j=1}^{n}c_{i}x_{j}+\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}q_{ij}x_{i}x_{j}.$
(4.15)

The Quadratic unconstrained binary optimisation (QUBO) above, also known as an
unconstrained binary quadratic programming (UBQP), is a combinatorial
optimisation problem with a wide range of applications from finance and
economics to machine learning is a specific case of Quadratic Programming with
binaries variables. We will analyse it deeply in section (9.1.1).

#####  4.3.2 Change of variables to simplify the quadratic formulation

In some cases, to simplify the objective function and therefore simplify the
programming of the algorithm, it is required to make some variable changes
(see Fig. (4.1)). This contribution is analysed below.

Figure 4.1: Variable change to simplify quadratic programming

Next, the change of variables is studied to simplify quadratic programming.
These variable changes and linear algebra tricks will help model our problem
into ”quantum” programming.

The matrix that defines an arbitrary quadratic problem can be expressed as a
symmetric matrix $A$. Because it is symmetric, it will be diagonalisable. That
is, there will be an invertible matrix $P$ and another diagonal $D$ such that:

$A=PDP^{-1}.$ (4.16)

The matrix $P$ acts as a base change, and if $A$ represents the quadratic
problem in the initial base, $D$ will define the problem for the new base.
Said matrix $D$ drastically simplifies the formulation and, therefore, the
computation.

Given the quadratic function $Q(x)=2x_{1}^{2}-4x_{1}x_{2}+5x_{2}^{2}$ we will
perceive what happens with the variable changes. Let us imagine for a moment
that the function $Q(x)$ is the Hamiltonian of the Ising model of the TSP.

Let us find the matrix $A$.

$Q=\left[\begin{matrix}2&5\\\ -2&5\\\ \end{matrix}\right]$ (4.17)

How is $A$ found? Following this trick:

$A=\left[\begin{matrix}a&c\\\ d&b\\\ \end{matrix}\right].$ (4.18)

If we consider the function $Q(x)$, $a$ is the constant that multiplies
$x_{1}^{2}$ and $b$ is the term that multiplies $x_{2}^{2}$; $a=2$ and $a=5$.
So far, relatively easy. How are $c$ and $d$ determined? $c$ and $d$ are half
the coefficient of $x_{1}x_{2}$. So, $c=\frac{4}{2}=d$. From here are the
values and eigenvectors to be able to change the variables.

Given the characteristic polynomial $P(\lambda)=\text{det}(A-\lambda I_{n})$
if we want to calculate the eigenvalues, the characteristic polynomial must be
zero. This translates to $\det(A-\lambda I_{n})=0$, where $I_{n}$ is the
identity matrix of rank $n$ and $\lambda$ the eigenvalue. Mathematically
speaking, if we want the characteristic polynomial of matrix $A$ to be null,
the following linear equation must be solved. The characteristic polynomial is
of rank $n$, and its roots are the eigenvalues of matrix $A$. Since in our
case matrix $A$ is of rank 2, it will not be necessary to apply the Laplace
expansion formula. Starting from a square matrix of degree $n$.

$\det\left(A-\lambda I_{n}\right)=0.$ (4.19)

According to Laplace’s theorem, the value of its determinant is equal to the
sum of the products of the elements of a row or column by their attachments,
thus taking any row $f$, the determinant is:

$\det(P)=\sum_{j=1}^{n}a_{f,j}P_{f,j}.$ (4.20)

And taking a column $c$, it will be:

$\det\left(P\right)=\sum_{i=1}^{n}a_{i,c}P_{i,c}.$ (4.21)

Returning to our case, solving the equation of the characteristic polynomial
we get:

$\det\left(\begin{matrix}2-\lambda&-2\\\ -2&5-\lambda\\\
\end{matrix}\right)=0.$ (4.22)

Since it is a rank two matrix, the calculation of the determinant is direct
and is shown through the following quadratic expression:

$\lambda^{2}-7\lambda+6=0.$ (4.23)

Where the roots of the equation are $\lambda_{1}=1$ and $\lambda_{2}=6$. Now
let us calculated the eingenvectors of the matrix $A$.

$\exists~{}v\left({\begin{matrix}x_{1}\\\ x_{2}\\\ x_{3}\\\ \vdots\\\
x_{n-1}\\\ x_{n}\\\ \end{matrix}}\right)\neq
0\quad/\quad\exists~{}\lambda\in\mathbf{C}:\quad A\cdot v=\lambda\cdot v.$
(4.24)

Where $\lambda$ is the eigenvalue, $v$ is the eigenvector, and, if this
definition is applied, it arrives at (4.25):

$\left[\begin{matrix}2&5\\\ -2&5\\\
\end{matrix}\right]\left(\begin{matrix}x_{1}\\\ x_{2}\\\
\end{matrix}\right)=\lambda\left(\begin{matrix}x_{1}\\\ x_{2}\\\
\end{matrix}\right).$ (4.25)

With this expression $-2x_{1}=x_{2}$, we can find the two eigenvectors
associated with matrix $A$.

$v_{1}=\left(\begin{matrix}1\\\ -2\\\
\end{matrix}\right)\text{and}~{}v_{2}=\left(\begin{matrix}2\\\ 1\\\
\end{matrix}\right).$ (4.26)

Once this point has been reached, if the quadratic form is rewritten, the
reader can understand how simple it is and, consequently, its resolution or
programming will also be more straightforward.

$P(y)=\lambda_{1}y_{1}^{2}+\lambda_{2}y_{2}^{2}.$ (4.27)

Let us recall $Q(x)=2x_{1}^{2}-4x_{1}x_{2}+5x_{2}^{2}$, and find the matrix
$P$.

$P=\left[\begin{matrix}1&2\\\ -2&1\\\ \end{matrix}\right].$ (4.28)

If the matrix $P$ is normalised, the following expression is reached,

$P=\frac{1}{\text{dist}}\left[\begin{matrix}1&2\\\ -2&1\\\
\end{matrix}\right].$ (4.29)

With $\text{dist}=\sqrt[]{1^{2}+(-2)^{2}}$ as the distance.

$P=\frac{1}{\sqrt[]{5}}\left[\begin{matrix}1&2\\\ -2&1\\\
\end{matrix}\right].$ (4.30)

Retrieving the expression, $A=PDP^{T}$ takes us to $D=P^{T}AP$, where D is the
following matrix:

$D=\left[\begin{matrix}6&0\\\ 0&1\\\ \end{matrix}\right].$ (4.31)

These variable changes help simplify the objective function by undoing the
crossed variables.

####  4.4 Quadratic programming with quadratic constraints

The quadratically constrained quadratic program can be defined as an
optimisation problem in which both the objective function and the constraints
are quadratic functions.

When the constraints are of order 1, the quadratic formulation just analysed
works for us. But there are cases when the restrictions must be quadratic; of
the type $x_{1}\left(x_{1}-1\right)\leq 0$ and $x_{1}\left(x_{1}-1\right)\geq
0$ being equivalent to the constraint $x_{1}\left(x_{1}-1\right)=0$, and, in
turn, equal to the restriction $~{}x_{1}\in\\{0,1\\}$. In this case, a
generalisation of quadratic programming must be used. Almost for all quantum
algorithms where we want to improve resolution and computation time,
Quadratically Constrained Quadratic Program (QCQP) should be used. It is the
same studied so far but with quadratic restrictions. For this, the new
objective function $P(x)$ must be minimised

$\text{min}\quad P\left(x\right)=\frac{1}{2}x^{T}P_{0}x+q_{0}^{T}x+r_{0}.$
(4.32)

Subject to:

$\frac{1}{2}x^{T}P_{i}x+q_{i}^{T}x+r_{i}\leq 0\quad\text{for}\quad
i=1,\ldots,m,$ (4.33) $Ax=b.$ (4.34)

$P_{i}\in S_{+}^{n}$, the objective and constraints are quadratic convex,
where $\\{P_{0}{\dots,}P_{m}\\}$ are matrices $n\times n$ and $x\in R^{n}$ is
the optimisation variable. If $\\{P_{1}{\dots,}P_{m}\\}\in S_{++}^{n}$, the
feasible region is the intersection of $m$ ellipsoids and a cognate set.

When trying to model a problem into binary variables, a degree greater than
two may appear in the function to minimise. As most of the quantum computing
technique in this NISQ era is implemented to handle terms of degree less than
or equal to 2, the degree of monomials that do not meet this condition must be
reduced.
Let us analyse different ways to transform a cubic monomial of the cost
function into a quadratic one. Once we have this technique, applying it
repeatedly, we can decrease the degree of any monomial.

A first way is to transform the problem $\min f(w)$ into the problem $\min
g(k)$ subject to $t=xy$ con $f(w)=xyz$ y $g(k)=tz.$

Later, we will realise that we cannot have a quadratic constraint, so let us
find a way to substitute $t=xy$ for linear constraints.

Taking the constraints $t\leq x$, $t\leq y$ and $t\geq x+y-1$, we can
transform the problem of $\text{minimize}f(w)$ into the problem:

$\text{minimize}\quad tz$

,

$\text{subject to}\left\\{\begin{array}[]{c}t\leq x\\\ t\leq y\\\ t\geq
x+y-1.\end{array}\right.$

This remodelling involves introducing three inequality constraints. Inequality
constraints, while often unavoidable, are somewhat inefficient. This is due to
the need to include a set of auxiliary slack variables necessary to transform
each inequality into equality. This procedure is similar to the one that
occurs when modelling a linear programming problem to be solved using the
simplex algorithm. There are more techniques, but we will not dive deeply into
them in this thesis. Therefore, let us analyse for other better methods that
allow us to reduce the degree of the monomials.

The first technique we will analyse is to exploit the relationship

$f(w)=\max_{t\in\\{0,1\\}}\\{t(x+y+z-2)\\}.$

This relationship follows from the fact that, on the one hand, if any of the
variables $x,y,z$ is equal to $0$, we have that $(x+y+z-2)\leq 0$ and
therefore, the maximum on the right will be reached when $w$ takes the value
$0$, resulting in $0$. If, otherwise, all the variables are worth $1$, we
would have the product $w\cdot 1$, which takes the maximum value $1$ when
$t=1$.

Now, if the monomial $axyz$ from which we want to reduce the degree has
coefficient $a<0$, it is true that:

$\min_{x,y,z}axyz=a\max_{x,y,z}(xyz)=a\max_{x,y,z}(\max_{t}(t(x+y+z-2)))=a\max_{x,y,z,t}(t(x+y+z-2))=\min_{t,x,y,z}at(x+y+z-2).$

Therefore, if $a<0$ we can simply substitute monomials of the form $af(w)$ for
$a(t(x+y+z-2))$. If $a>0$ we cannot use the same technique since, although

$f(w)=-\min_{t\in\\{0,1\\}}t(-x-y-z+2),$

The above equation with the minus sign does not allow this term to be entered
in the cost function.

To solve this problem, let us return to the problem of expressing the equation
$z=xy$ in linear terms. The penalty functions are needed in these cases. We
need to construct a penalty function that takes large values when $z\neq xy$
and the value $0$ when $z=xy$. Also, it is needed to work carefully on
Lagrange multiplier. This task is important for problems where the degree of
the restriction can be greater than 2; Problems that go beyond those of this
NISQ era.

Most problems of interest include additional constraints and many of these
problems can be re-formulated (re-casted) as a QUBO model by introducing
quadratic penalties with a positive scalar $P$. The table (4.1) summarises the
widely used penalties function.

Classical Constraint | Equivalent Penalty
---|---
$x=y$ | $P(x+y-2xy)$
$x+y=1$ | $P(1-x-y+2xy)$
$x+y\leq 1$ | $P(xy)$
$x+y\geq 1$ | $P(1-x-y+xy)$
$x\leq y$ | $P(x-xy)$
$x_{1}+x_{2}+x_{3}\leq 1$ | $P(x_{1}x_{2}+x_{1}x_{3}+x_{2}x_{3})$
Table 4.1: In this table, we see the most used and known penalties. It is
worth mentioning that binary variables satisfy $x_{i}^{2}=x_{i}.$

####  4.5 Summary

In this chapter, we have analysed and studied the methods of solving
combinatorial optimisation algorithms. Furthermore, we have studied Linear
Programming and its derivative of binary integers, Quadratic Programming and
Quadratic Programming with Quadratic Constraints. But here, we have not
studied a lead combinatorial optimisation problem-solving algorithm, QUBO.
However, the reader can find it in the section (9.1.1) on quantum computing
because of its close connection with the Ising models. Moreover, QUBO is a
problem central to adiabatic quantum computing, where it is solved by a
physical process called quantum annealing. This model is very interesting for
quantum computing for its easy mapping to the Ising model.

We can now entirely focus and delve into quantum computing, but to do this, we
will introduce some necessary concepts and theories of quantum mechanics.

###  Chapter 5 Introduction Quantum Mechanics

####  5.1 Introduction

Quantum mechanics [Bes12] is a theory that describes the physical properties
of nature on an atomic scale.

This section will give a complete description of the basic postulates of
quantum mechanics. These postulates are important to connect the physical
world and the mathematical formalism of quantum mechanics. First of all, we
will review the limitation faced by Moore’s law. Then we will analyze the
state of quantum technologies. Finally, and before focusing on the postulates
of quantum mechanics, we will briefly introduce the era in which quantum
computing finds itself.

The first revolution [118] of quantum mechanics is the basis of several
advances to our modern society. Almost all modern electronics in the last 50
years have been based on the properties of quantum mechanics. Semiconductors
such as diodes, transistors, integrated circuits, etc., have led to the
considerable growth of electronics today.

Quantum mechanics, in addition to studying the motion of particles, also
allows us to understand the properties of materials and their features to
manufacture transistors. These are the basis of all modern electronics and the
control system of millions of devices that we use today. However, in this
thesis, we focus on the second revolution of quantum mechanics, that is, in
using the properties of quantum mechanics to empower computing (5.1).

Figure 5.1: TBluefors dilution refrigerators used in the MIT Engineering
Quantum Systems group to operate superconducting qubits at near-zero
temperatures [213]

The Quantum information science also known as QIS, is the area of information
science that depends on the effects of quantum mechanics. During the last
decades, the scientific community has dedicated a lot of time and has provided
considerable resources to QIS [226]. As a result of this delivery,
improvements have been achieved in the scientific advances that we see
reflected in publications, conferences, and concrete solutions such as D-Wave,
IBMQ, Xanadu, etc. Quantum computing, in particular, and quantum information
science is a hot topic because of its novelty and the promising developments
it predicts.

In this thesis work, all the postulates of quantum mechanics on which we rely
are referenced by [164].

####  5.2 Moore Law

Another aspect to consider understanding the importance of the properties of
quantum mechanics and thus empower computing is Moore’s law, which states that
the number of transistors that can be integrated into a single chip doubles
every 18 months. This process Figure (5.2) leads to a doubling of the memory
and a doubling of the calculation speed. Therefore, it is expected that the
size of the characteristic of the wafer (thin plate of semiconductor material)
will be less than 10nm during this year (2020). At this point, the individual
properties of atoms and electrons would begin to dominate, so Moore’s law
would no longer be valid. Therefore, the demands of the miniaturisation of
electronics will eventually bring us to the point where quantum effects become
important [226].

Figure 5.2: Moore law Roadmap: Quantum Computing Stack Exchange [178]

Because Moore’s law will stop working today, there are even more reasons for
the scientific community to resort to QIP much sooner than it seems [226,
Iva12]. On the other hand, multi-core architecture is becoming a practical
approach; computational speed improvement can be achieved even without
reducing the size of the feature by parallelisation.

Figure 5.3: The number of research papers published per year in quantum
computing and technologies [198]

#####  5.2.1 State of the Quantum Technologies

Another point to highlight is the fact that, despite the intensive development
of quantum algorithms, the number of available quantum algorithms is still
small (Fig. (5.3)) compared to that of classical algorithms basically because
the current quantum gates are only several tens of quantum bits (qubits),
which is relatively low for any significant quantum computing operation [181].

Figure 5.4: Quantum Computing is becoming the talk of the town [3] Figure 5.5:
The number of qubits achieved by date and organisation. Roadmap by YOLE
Development [84]

This delay was partial until very recently, and it was believed that quantum
computing would never or seldom come true. However, the latest advances in the
different techniques (D-Wave, IBMQ, Xanadu, …) of quantum gate
implementations, as well as the proof of the precision threshold theorem
[147], give rise to optimism (Figures (5.4) and (5.5)) that quantum computers
(5.1) to large-scale could become a reality quite soon [181]. We can also
appreciate (Figures (5.6) and (5.7) ) the metrics and milestones to help
monitor the development of quantum computing and the companies and startups
involved in the 2018 quantum computing ecosystem.

One of the most significant problems that QIS faces is the physical deployment
issues. There are many potential technologies, such as nuclear magnetic
resonance (NMR), ion traps, quantum cavity electrodynamics, photonics, quantum
dots, and superconducting technologies, to name just a few. However, it is not
clear which technology will prevail. For example, Xanadu (photonics)
technology seems to be most likely for quantum teleportation [120, 216].

Right now, there is a big battle going on between the significant
manufacturers of quantum computers to achieve the highest number of qubits and
’impose’ their scalability plan. In knowing who will be able to define the
standard and, above all, get the quantum supremacy [18].

####  5.3 Noisy Intermediate-Scale Quantum

The Noisy Intermediate-Scale Quantum era known as (NISQ) era [181], is defined
as the era leading quantum processors to contain about 50 to a few hundred
qubits. Still, it is not advanced enough to reach fault tolerance nor large
enough to profit sustainably from quantum supremacy. It is used to describe
the current state of the art in the fabrication of quantum processors.

To summarise, the computers are challenging to achieve, and in the near term,
there will NISQ computers with limited performance. To seize quantum computing
during the NISQ era, algorithms with low resource demands and capable of
returning approximate solutions are explored. In addition, quantum states
cannot be indefinitely maintained over time, and the purely quantum properties
are steadily lost during the execution of a quantum algorithm. Until the
present time, the two greatest achievements are the double accomplishment of
the so-called quantum supremacy, that is, using a quantum computer to solve a
problem more efficiently and with better performance than any classical
computer. This means that the devices in the NISQ era are not expected to be
more powerful and change the world by themselves but rather to be an
intermediate step towards a new generation of computers.

The real problem of this era is related to decoherence [59]. Decoherence is
associated with the interaction of qubits with environments that blur the
fragile states of overlap (entanglement). This results in the introduction of
random errors due to the environment. However, there are quantum error
correction techniques known as the Quantum Error Correction Concept (QECC)
[Bes12, 63]. One of the powerful applications of quantum error correction is
based on the protection of quantum information, as it is dynamically subjected
to quantum computing. Imperfect quantum gates affect quantum computing by
introducing errors into the computed data. Also, imperfect control gates add
errors into the processed sequences as incorrect operations can be applied.
However, this imperfection gives rise to exciting computing techniques and
algorithms based on variational calculations. This opens up a world of
possibility to the era of Quantum Machine Learning (QML) [39, Pet14, 195]. The
objective of QECC is to deal with errors introduced by quantum channels and
those presented by (imperfect) quantum gates during the encoding and decoding
process. Because of this, the reliability of the data processed by quantum
computers depends on the probability of error per gate being below a certain
threshold known as the precision threshold theorem. This is what NISQ defines
as. ’Noisy’ because we don’t have enough qubits leftover for error correction,
so we’ll have to use the imperfect qubits directly on the physical layer and
’Intermediate-Scale’ due to its reduced qubit (but not too small).

Figure 5.6: Metrics and milestones to help monitor the development of quantum
computing. Roadmap by MIT [198] Figure 5.7: Companies and startups involved in
the 2018 quantum computing ecosystem. Roadmap by Quantum World Association

To understand quantum mechanics, we have to appreciate its postulates. These
postulates provide a connection between the physical world and the
mathematical formalism of quantum mechanics. It is important to emphasise that
it is unnecessary to understand quantum mechanics in detail to know how to
make a program on a quantum computer. But if we want to make intelligent and
efficient algorithms, it is more than recommended to understand the
fundamentals of quantum mechanics. The analogy to understand what we mean is
the following: To program we can do it in PhP, and python, high-level
languages, but we can also program in C or in assembler (machine language). If
we want to be experts or make efficient algorithms, it would be useful to know
the machine’s architecture and to program in the machine language.

In the next section, we will present the postulates of quantum mechanics
necessary to understand and, above all, delve into quantum computing. This
thesis is based on the postulates listed in this reference [164] Quantum
Computation and Quantum Information

####  5.4 Postulate 1

The postulate 1 is defined as associated with any isolated physical system is
a complex vector space with an internal product (Hilbert space) known as the
state space of the system. The system is fully described by its state vector,
which is a unit vector in the state space of the system.

This postulate explains the space of the quantum state and describes the area
where quantum mechanics takes place. This area is nothing more than linear
algebra in Hilbert vector space [220]. It is essential to know that, given a
physical system, quantum mechanics does not tell us what the state space of
that system is, nor can it tell us what the system’s state vector is.
Therefore, it is imperative to have this clear postulate. In other term, what
we mean is that it is challenging to know the state of a quantum system at all
times.

Let’s consider that the simplest quantum mechanical system is the qubit. A
qubit has a two-dimensional state space $|0\rangle$ and $|1\rangle$ that form
an orthonormal basis for that state space. Then you can write an arbitrary
state vector in the state space.

$|\psi\rangle=a|0\rangle+b|1\rangle.$ (5.1)

Where $a$ and $b$ are complex numbers. The condition that $|\psi\rangle$ is a
unit vector is given by $\langle\psi|\psi\rangle=1$, is therefore equivalent
to $|a|^{2}+|b|^{2}=1$. The term $\langle\psi|\psi\rangle=1$ is known as the
normalisation condition for state vectors.

The way a qubit differs from a classic bit is that there are overlaps of these
two states, in the form $a|0\rangle+b|1\rangle$ , where it is not possible to
say that the qubit is definitely in the state $|0\rangle$, or definitely in
the state $|1\rangle$. In other words, what we mean is that the quantum state
is a linear combination of the components $a$ and $b$.

If we had a system of more than one qubit, the expression of the quantum state
would be of the form $\sum_{i}a_{i}|\psi_{i}\rangle$, and we would have a
system with the superposition of the states $|\psi_{i}\rangle$ and of
amplitude $a_{i}$ for the state $|\psi_{i}\rangle$.

####  5.5 Postulate 2

The postulate 2 is defined as a unitary transformation describes the evolution
of a closed quantum system. That is, the state $|\psi\rangle$ of the system at
the time $t_{1}$ is related to the state $|\psi^{{}^{\prime}}\rangle$ of the
system at the time $t_{2}$ by a unit operator $U$ that depends only on times
$t_{1}$ and $t_{2}$, $|\psi^{{}^{\prime}}\rangle=U|\psi\rangle$. This
postulate gives a standard for describing quantum state changes over time.

From Ref. [165] we know that quantum mechanics does not tell us the state
space or quantum state of a particular quantum system; it also does not tell
us which unit operators $U$ describe real-world quantum dynamics. On the other
hand, quantum mechanics assures us that the evolution of any closed quantum
system can be described in this way.

$|\psi^{{}^{\prime}}\rangle=U|\psi\rangle.$ (5.2)

In a way, we are saying that if we want to describe an $n$ qubit quantum
system subject to time evolution, we must calculate its unit operators $U$.
The challenge would be to find such unit operators. Quantum gates are somehow
the operators that act on quantum states. This postulate is very interesting
and requires that the quantum system be closed [Bes12][Pau18]. Moreover,
various derivatives emerge from this postulate.

#####  5.5.1 Postulate 2’

The postulate 2’ is defined as the time evolution of the state of a closed
quantum system is described by the Schrödinger equation (5.3).

$i\hbar\frac{\delta|\psi\rangle}{\delta t}=H|\psi\rangle.$ (5.3)

Where $\hbar$ is Planck’s constant and $H$ is a fixed hermitian operator known
as the Hamiltonian of the closed system [Bes12].

In some way, we can say that if we know the Hamiltonian of a system, then we
understand its dynamics completely. This concept is precious for modelling the
system, and we will use it a lot throughout our thesis.

During the 20th century, much of the scientific (physical) community has been
dedicated to discovering the Hamiltonian of any quantum system. And the
conclusion they reached is that, in general, finding out that the Hamiltonian
necessary to describe a particular physical system is challenging.

The Hamiltonian is static and a Hermitian operator that allows us to make its
spectral decomposition with eigenvalues of energy E and the normalised
eigenvectors corresponding to energy $E$ as eigenstates $|E\rangle$.

$|H\rangle~{}=\sum_{E}E|E\rangle\langle E|,$ (5.4)

$|E\rangle=exp(-i\frac{Et}{\hbar})|E\rangle.$ (5.5)

The equation (5.5) is valid only in the case of having a static Hamiltonian.
The lowest energy is known as the ground state energy for the system, and the
corresponding energy proper state (or adequate space or steady-state) is known
as the ground state.

$|\psi(t_{2})\rangle=exp[\frac{-iH(t_{1}-t_{2})}{\hbar}]|\psi(t_{1})\rangle=U(t_{1}-t_{2})|\psi(t_{1})\rangle.$
(5.6)

Where we define

$U(t_{1}-t_{2})\equiv exp[\frac{-iH(t_{1}-t_{2})}{\hbar}].$ (5.7)

This interpretation is compelling and extremely useful since it is shown that
any unitary operator $U$ can be written in the form (5.8) tanking $\hbar=1$
and $t_{2}=0$ the equation comes out to be (5.6)

$U=exp(-iK).$ (5.8)

With $K$, a Hermitian operator.

####  5.6 Postulate 3

The postulate 3 is defined as quantum measurements are described using a
${M_{m}}$ collection of measurement operators. These are the operators that
operate in the state space of the system being measured. The $m$ index refers
to the measurement results in the experiment. If the state of the quantum
system is $|\psi\rangle$ immediately before the measurement, the probability
that the result $m$ will occur is given by the equation (5.9).

$p(m)=\langle\psi|M_{m}^{T}M_{m}|\psi\rangle.$ (5.9)

The state of the system after the measurement is (5.10).

$\frac{M_{m}|\psi\rangle}{\sqrt[]{\langle\psi|M_{m}^{T}M_{m}|\psi\rangle}}.$
(5.10)

And, the measurement operator satisfies the completeness equation [Bes12] that
is given by the following equation (5.11) for all the values of the quantum
state $|\psi\rangle$.

$\sum_{m}M_{m}^{T}M_{m}=Ip(m)=\langle\psi|M_{m}^{T}M_{m}|\psi\rangle=1.$
(5.11)

The value of the measure is the probability described by $|a|^{2}+|b|^{2}=1$.

If we want to make the different $M_{m}$ observations, the operations we would
be doing are the following:

$M_{0}=|0\rangle\langle 0|=\begin{bmatrix}1\\\
0\end{bmatrix}\begin{bmatrix}1&0\\\ \end{bmatrix}=\begin{bmatrix}1&0\\\ 0&0\\\
\end{bmatrix}.$ (5.12)

$M_{1}=|1\rangle\langle 1|=\begin{bmatrix}0\\\
1\end{bmatrix}\begin{bmatrix}0&1\\\ \end{bmatrix}=\begin{bmatrix}0&0\\\ 0&1\\\
\end{bmatrix}.$ (5.13)

With $\langle\psi|$ the conjugate of $|\psi\rangle$, represented by
$|\psi\rangle=\langle\psi|^{T}$

$M_{0}|0\rangle=|0\rangle\langle 0|0\rangle=\begin{bmatrix}1&0\\\ 0&0\\\
\end{bmatrix}\begin{bmatrix}1\\\ 0\\\ \end{bmatrix}=\begin{bmatrix}1\\\ 0\\\
\end{bmatrix}=|0\rangle.$ (5.14)

$M_{0}|1\rangle=|0\rangle\langle 0|1\rangle=\begin{bmatrix}1&0\\\ 0&0\\\
\end{bmatrix}\begin{bmatrix}0\\\ 1\\\ \end{bmatrix}=\begin{bmatrix}0\\\ 0\\\
\end{bmatrix}=0.$ (5.15)

knowing that $|0\rangle\bot|1\rangle$, $\langle 0|1\rangle$ disappears; It is
cancelled. If we project on any state, we will have:

$M_{0}|\psi\rangle=|0\rangle\langle 0|\psi\rangle=|0\rangle
a|0\rangle+b|1\rangle=a|0\rangle.$ (5.16)

We can generalise (5.14): let $M_{0}$, let $i$ be any qubit and let
$|\psi\rangle$ be a multi-state of qubits, the measurement or the projection
on the state $|0\rangle$ can be expressed as:

$Tr\begin{bmatrix}|\psi\rangle\langle\psi|M_{0}^{i}\\\ \end{bmatrix}.$ (5.17)

If the qubit $i$ is measured in the state $|0\rangle$, then the system will be
in the state expressed by (5.18).

$\frac{M_{0}^{i}|\psi\rangle}{\|M_{0}^{i}|\psi\rangle\|_{2}}.$ (5.18)

Another way to get the result of the measurements is to remember that the
measurement operator is Hermitian; this translates to $M_{0}^{2}=M_{0}$ the
same for $M_{1}^{2}=M_{1}$. Also remembering that the relationship of
completeness obeys the equation $I=M_{0}^{T}M_{0}+M_{1}^{T}M_{1}=M_{0}+M_{1}$.

One of the crucial applications of (5.6) is to distinguish quantum states. We
recall that since the quantum system must be closed (5.4)), getting to find