In this paper, the problem of charging electric motor vehicles on a motorway is considered. Charging points are located alongside the motorway. It is assumed that there are a number of vehicles on a given section of a motorway. In the motorway, there are several nodes, and for each vehicle, the entering and the leaving nodes are known, as well as the time of entrance. For each vehicle, we know the total capacity of its battery, and the current amount of energy in the battery when entering the motorway. It is also assumed that for each vehicle, there is a finite set of speeds it can use when traveling the motorway. The speed is chosen when entering the motorway, and cannot be changed before reaching the charging station. For each speed, there is given a corresponding power usage; the higher the speed, the larger the power usage. Each vehicle can only use one charger, and when its battery is full, the amount of energy is sufficient for reaching the outgoing node. We look for a feasible solution to the problem, i.e., a solution in which no vehicle has to wait for a charger. The problem is formulated as a problem of scheduling independent, nonpreemptable jobs in parallel, unrelated machines under an additional doubly constrained resource, which is power. Quantum approaches to solve the defined problem are proposed. They use the quantum approximate optimization algorithm and the quantum annealing technique. A computational experiment is presented and discussed. Some conclusions and directions for future research are given.

Quantum optimization is a significant area of quantum computing research with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational-Hamiltonian-based algorithms, struggle to present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning, but they often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for a quantum approximate optimization algorithm that satisfies all the requirements to correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities for finding solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in a linear instead of exponential number of entanglement gates instead and superior performance compared to standard formulations. Specifically, we achieve a higher probability of finding feasible solutions: finding solutions in nine out of nine instances compared to standard Hamiltonian formulations and quadratic programming formulations known from quantum annealers, which only found solutions in seven out of nine instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future.

Quantum optimization is a significant area of quantum computing with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational Hamiltonian-based algorithms, struggle on present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning but often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for the Quantum Approximate Optimization Algorithm to satisfy all the requirements that correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities of measuring solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in linear number of entangleming gates instead of exponential and superior performance compared to standard formulations. Specifically, we achieve higher probabilities of measuring feasible solutions in 9 out of 9 instances compared to standard Hamiltonian formulations and surpass quadratic programming formulations known from quantum annealers in 7 out of 9 instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future.

Current technological advancements of quantum computers highlight the need for application-driven, practical and well-defined methods of benchmarking their performance. As the existing NISQ device's quality of two-qubit gate errors rate is even around one percent and the number of qubits is still limited to a few or several dozen, naturally, we need to propose rather small algorithms instances taken from key promising application areas, such as quantum chemistry, combinatorial optimisation or machine learning. While many techniques for assessing the performance of logical components, such as gate fidelity and qubit coherence exist, it is still challenging to extrapolate those values onto the performance of different quantum algorithms and subroutines. This work aims to introduce a series of initial quantum application benchmarks together with a methodology of execution for measuring the performance and fidelity of the results. The proposed suite refers to several variational algorithms widely used on available NISQ devices but also includes examples of quantum circuits designed for a fault-tolerant quantum computer.