The application of quantum algorithms on some problems in NP promises a significant reduction of time complexity. This thesis uses Grover’s Algorithm, originally designed to search an unstructured database with quadratic speedup, to find valid solution bit-strings to the NP-hard personnel scheduling problem. Under consideration of various hard and soft constraints, we implement this by using the IBMQ backend and Qiskit to optimize the German Aerospace Center’s spacecraft on-call operator scheduling. We seek an optimal assignment for 52 operators to 17 positions over a period of 180 days under constraints on schedule and personnel. Further, we evaluate the solution quality and compare the performance with classical and quantum alternatives. While still restricted by intermediate scale quantum devices in the near term, we explore new approaches in encoding and batching the problem to reduce the required number of qubits. In the end, a feasible near-term solution that scales well with the quantum devices of the upcoming years is presented.
The application of quantum algorithms on some problems in NP promises a significant reduction of time complexity. This thesis uses Grover’s Algorithm, originally designed to search an unstructured database with quadratic speedup, to find valid solution bit-strings to the NP-hard personnel scheduling problem. Under consideration of various hard and soft constraints, we implement this by using the IBMQ backend and Qiskit to optimize the German Aerospace Center’s spacecraft on-call operator scheduling. We seek an optimal assignment for 52 operators to 17 positions over a period of 180 days under constraints on schedule and personnel. Further, we evaluate the solution quality and compare the performance with classical and quantum alternatives. While still restricted by intermediate scale quantum devices in the near term, we explore new approaches in encoding and batching the problem to reduce the required number of qubits. In the end, a feasible near-term solution that scales well with the quantum devices of the upcoming years is presented.
Scheduling medical staff in healthcare institutions is a complex and critical task that requires balancing operational constraints, personnel availability, quality of care, and staff well-being. These interdependent factors make the creation of optimal schedules particularly challenging necessitating sophisticated approaches that effectively reconcile institutional needs and medical staff expectations. This project explores an innovative alternative approach: quantum optimization. By formulating the scheduling problem as a QUBO (Quadratic Unconstrained Binary Optimization) model, we aim to leverage the capabilities of quantum algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA) This framework allows constraints and objectives to be reformulated as quadratic functions, facilitating their integration into Ising models and their resolution on quantum gate_based circuit systems.To this end, we implement a hybrid quantum-classical solution using QAOA on IBM’s Qiskit platform. We analyze QAOA’s performance on problem instances of up to 27 qubits, and compare it against classical solvers such as CPLEX. Through this comparative approach, we assess the practical viability of quantum optimization in medical staff scheduling and contribute to the broader investigation of quantum computing in operational planning within healthcare systems.
Optimization is central to urban mobility, where ride-sharing platforms must continuously match passengers with vehicles under complex constraints such as destination compatibility, cost, route efficiency, and acceptable waiting time. Classical exact methods like integer programming scale poorly as the problem size grows and struggle with highly dynamic inputs such as fluctuating demand, travel times, and vehicle capacities. Quantum computing offers an alternative paradigm: by exploiting superposition and interference, quantum search algorithms can explore large combinatorial spaces more efficiently than classical brute-force search. This study presents a proof-of-concept quantum formulation of a foundational ride-sharing assignment problem and investigates the use of Grover’s search algorithm. The model considers five unique passengers (Mehmet, Aytuğ, Filiz, Alara, and Ayliz) and two vehicles. Each passenger must be assigned to one of the two vehicles, subject to a balanced distribution objective (either a 3–2 or 2–3 split) and individual feasibility constraints. The problem is encoded on a 5-qubit quantum register, where the state of each qubit (|0⟩ or |1⟩) denotes assignment to Vehicle A or Vehicle B, mapping the full 2⁵ = 32-state Hilbert space to all possible allocations. A Grover oracle is designed to “mark” all assignments that satisfy the balanced-split and feasibility conditions by applying a phase flip to those computational basis states. The algorithm is implemented and simulated using IBM’s Qiskit framework. The results show that, after two Grover iterations, the total probability of measuring one of the ten valid “balanced” states increases from 31.25% to over 95%, in line with the expected quadratic speed-up of Grover’s algorithm over classical exhaustive search, which requires O(N) evaluations for N = 32 states. Although intentionally simplified—excluding realistic factors such as travel times, traffic, capacities, and time windows—this work demonstrates that a vehicle-sharing assignment problem can be cast as a quantum search task. Future work will focus on scaling to larger instances, incorporating richer operational constraints, and exploring quantum-classical hybrid approaches for real-world logistics optimization.
There exist several quantum algorithms with a proven quantum advantage. One of them is the Grover Search Algorithm [1], which finds an item in an unordered database with quadratic speed-up. By mapping optimization problems to search problems, one is able to harvest this quantum advantage. A particularly interesting NP-hard problem explored in the project QCMobility is the lock scheduling problem. Here we aim at deriving an optimal schedule to lock the incoming ships, while minimizing for example waiting times or water consumption. In this poster, we investigate the solution of the lock scheduling problem. For this purpose, we formulate it as a quadratic unconstrained binary optimization (QUBO) problem and find the global optimum with Grover Adaptive Search [2]. Our results are obtained on quantum hardware simulators. [1] L. K. Grover, Proc. 28th Annu. ACM Symp. Theory Comput., 212 - 219 (1996). [2] W. P. Baritompa, D. W. Bulger, and G. R. Wood, SIAM J. Optim. 15, 1170 (2005).
Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
Quantum computing is a rapidly growing field, promising computational advancements with significant impact on real-world and industrial applications. These areas include cryptography, financial systems, material and drug discovery. They also cover combinatorial optimization, which is the focus of this thesis. For combinatorial optimization problems, researchers have spent several decades extending the capabilities of quantum algorithms for both near-term and far-term quantum hardware. Because current devices comprise too few qubits (quantum bits) and noisy gates (qubit operations prone to errors), potential quantum advantage must be assessed using theoretical and numerical frameworks. Despite the existence of many quantum algorithms, such as Grover’s algorithm and Quantum Branch-and-Bound (QB&B), which provide asymptotic speedups, we lack evidence of a practical quantum speedup on realistic problem instances. Recent benchmarking efforts show that several far-term algorithms with asymptotic advantage still cannot achieve practical quantum advantage under realistic conditions. This thesis comprises three advancements. First, it develops a new type of state preparation tailored to constraint optimization problems. This enables a Grover-based heuristic we call Constraint-oriented biased quantum search (CBQS). Second, it introduces benchmarking methods that compare the quantum search with state-of-the-art classical algorithms on large instances. These methods indicate that the proposed quantum algorithm can achieve a practical quantum advantage. For some cases, logical gate times of just 10−6s with about 19,000 logical qubits are enough to match classical runtime. Third, it presents a quantum circuit backend (software that processes quantum circuits) designed for speed at the cost of suboptimal circuit design. This backend outperforms a wide range of existing software packages in both speed and memory consumption, demonstrated by Quantum Fourier Transformation (QFT) circuits of up to 2000 qubits. Overall, this work points the way toward full-stack quantum advantage while underscoring the need for further research on topics such as quantum error correction.