The maximum-independent-set problem is a fundamental graph problem with applications in situations where one wants to select as many mutually compatible objects as possible, such as non-conflicting tasks or choices. This problem is computationally difficult to solve exactly on large graphs. This motivates the use of heuristic algorithms. However, heuristic performance can depend strongly on the structure of the input graph, so it is not enough to ask which algorithm performs best on average. It is also important to understand when and why a heuristic fails.

This Bachelor End Project studies heuristic algorithms for the maximum-independent-set problem from a structural point of view. We compare three methods: a minimum-degree Greedy algorithm, Lotka–Volterra dynamics, and simulated annealing, using an exact solver as a benchmark on small graphs. The goal is not only to compare solution sizes, but also to identify the graph structures and parameter choices that cause each method to perform poorly.

The results show that the algorithms fail for different structural reasons. Greedy can perform poorly when the minimum-degree rule is locally attractive but globally misleading. In the tested bad examples, Greedy selects vertices that look good by degree, but this choice blocks access to a much larger independent set. Lotka–Volterra dynamics can converge to maximal independent sets that are not maximum. This behavior is influenced by the initial condition and becomes more important when the graph contains many competing maximal independent sets. Simulated annealing is affected by the structure of the energy landscape. In particular, the experiments suggest that failure is not caused only by a single large energy barrier, but also by the presence of many competing trap states.

The parameter experiments support these interpretations. Increasing the Lotka–Volterra competition parameter τ strengthens early suppression between neighboring vertices but often leads to smaller independent sets. For simulated annealing, increasing the penalty parameter α makes edge conflicts more expensive and helps the algorithm reach feasible states earlier, but it can also reduce exploration through temporary conflict states. Longer cooling schedules improve performance, especially on larger or more crowded instances, but require more computation.

Overall, the thesis shows that the performance of maximum-independent-set heuristics cannot be explained by graph size alone. The relevant difficulty depends on graph structure, the number of competing maximal independent sets, the initial condition, and the algorithm parameters. This gives a more diagnostic view of heuristic performance: instead of treating Greedy, Lotka–Volterra, and simulated annealing as black-box methods, the thesis identifies structural warning signs that indicate when each method is likely to struggle. ... Read more

Quantum compilers are necessary to adapt quantum circuits to the connectivity and noise constraints of Noisy Intermediate-Scale Quantum devices. A key step in the compilation process is initial qubit mapping, where logical qubits are assigned to physical qubits. This assignment affects the overall reliability of the circuit, as mappings that place interacting qubits on non-adjacent physical qubits can require additional SWAP gates during routing. Recently, reinforcement learning techniques have been employed to tackle the initial qubit mapping problem. In this setting, the choice of reward function is particularly important, since it defines the objective the RL agent learns to optimize. This raises a central question for RL-based initial mapping: whether graph-level rewards can serve as useful proxies for downstream compiled-circuit quality. This work addresses this question by engineering reward functions based on hardware-distance and hardware-fidelity signals, including a hybrid reward that combines both, and evaluating how well they predict two downstream metrics: compiled SWAP count and estimated success probability (ESP). The same rewards are used to train action-masked PPO agents with terminal, shaped and (n)-step shaped variants on 5-qubit hardware topologies. Overall, the results show that graph-level rewards provide useful learning signals to guide RL-based initial mapping, but remain limited as proxies for full-compilation performance. This highlights the need for reward design that includes more routing relevant information, such as repeated interactions and gate ordering, to better approximate the effects of routing on final compiled-circuit quality. ... Read more

To run a quantum program on real hardware, a compiler must rewrite it so that every interacting pair of qubits is physically adjacent on the chip, which it does by inserting extra SWAP operations. How these SWAPs are chosen determines how reliably the program runs: each one adds gates and lengthens the schedule, and on today’s noisy devices both effects make a wrong answer more likely. Reliability thus depends on two costs at once, the program’s size and its running time, yet the routing pass that quantum compilers deploy, SABRE, optimises only the first: it minimises the number of SWAPs. The SWAP count stands in for size but not for running time, even though running time is the cost that limits reliability most on current hardware. Optimising it alone is a case of a pass tuning a convenient proxy rather than the quantity that ultimately matters.

We show this proxy gap is real and then close it. SABRE-MS keeps SABRE’s objective and adds the missing one, running time, so the router balances the two costs instead of ignoring one. A single tunable weight sets how much each of the two metrics, the program’s size and its running time, counts in the balance. It cuts a compiled program’s number of cycles by about 20% on average compared with the SABRE version that Qiskit ships. A standard reliability model shows the trade-off pays off despite the added operations, the gain holds as circuits grow to tens of qubits, and on a real 156-qubit IBM processor it raises the measured circuit fidelity by about 2.5×. The same idea, applied to a very different reinforcement-learning router, helps it in the same way, providing evidence that the benefit belongs to the objective rather than to SABRE itself. ... Read more

Running a quantum circuit on hardware with limited qubit connectivity requires inserting SWAP gates, each of which adds depth and exposes qubits to decoherence, so that two qubits that must interact become physically adjacent on the chip. Reinforcement learning (RL) is an increasingly used adaptive alternative to hand-engineered routing heuristics, but how an RL agent’s observation and action encodings should be designed has received little attention, even though environments such as qgym leave both choices to the user.

We study these two encodings one at a time. The first is observation reach, or how many upcoming gates the agent can see; the second is action-space granularity, ranging from single SWAPs through a heuristically pruned set to multi-SWAP macro actions. Holding the reward, algorithm, hyperparameters, and hardware constant, we evaluate both on the coupling graphs of a 7-qubit and a 16-qubit IBM device.

Observation reach has little effect on routing, and the full-circuit view performs poorly on the larger device. Action-space granularity matters much more: macro actions solve substantially more circuits and route them with fewer SWAPs, and this advantage grows with device size. Injecting the same routing heuristic as a soft prior on the action distribution, rather than as a hard mask, preserves completeness while roughly halving SWAP overhead. A disjoint held-out evaluation suggests these results reflect transferable routing skill rather than memorized training circuits. ... Read more

Compiling quantum circuits for physical hardware requires an initial mapping step that assigns virtual qubits to physical qubits such that interacting pairs are placed on connected hardware locations. Current approaches train a separate agent per device topology, requiring significant compute for each new hardware generation and transferring no knowledge across devices. This work investigates whether curriculum learning --- progressively training a reinforcement learning agent on hardware topologies of increasing size --- can produce a single agent that generalises to unseen topologies. We evaluate three curriculum variants differing in replay ratio and warmup length, alongside three non-curriculum baselines, in the QGym InitialMapping environment using MaskablePPO. Results show that curriculum agents outperform single-topology and single-size training on held-out topologies, reaching strong frontier performance with greater sample efficiency than direct training. Against unordered exposure to the same topology distribution, however, curriculum ordering's advantage holds on the target topology size but not on generalisation to unseen topologies. While absolute performance remains modest and variance across seeds is substantial, the findings establish curriculum learning as a viable approach to topology-general qubit mapping and provide a proof of concept for training a single model that transfers across hardware topologies, reducing the computational cost of re-training for each new device. ... Read more

Quantum gate scheduling assigns start cycles to quantum-circuit operations while respecting precedence, resource, and hardware constraints. Although schedules are commonly evaluated by makespan, it is only an indirect proxy for execution reliability, since schedules of equal duration may differ in gate errors, idle-time decoherence, and crosstalk exposure. This thesis investigates whether reinforcement learning benefits from domain knowledge in quantum gate scheduling. Building on qgym’s scheduling environment, we evaluate Maskable Proximal Policy Optimization against greedy ASAP and ALAP baselines on Random, GHZ, QFT, and QAOA circuit families using IBM calibration data. We study commutation-awareness, which relaxes unnecessary ordering constraints between commuting gates, and hardware-awareness, which injects calibration data through extended observations and/or a log-ESP-based reward. The main finding is that commutation-awareness is the most reliable improvement: it reduces makespan by approximately 20% for QAOA and Random circuits, while giving little benefit for GHZ and QFT circuits. Furthermore, noise-aware observation space proves promising for further research. ... Read more

Quantum computing holds the potential to revolutionize computation by leveraging quantum mechanical principles to solve problems intractable for classical computers.
However, current noisy intermediate-scale quantum (NISQ) devices are constrained by limited qubit connectivity, high gate error rates, and hardware-specific noise patterns.
One of the key challenges in quantum circuit execution is qubit routing—efficiently mapping logical qubits to physical qubits while adhering to connectivity constraints and minimizing error accumulation.
Traditional heuristic and rule-based transpilation techniques struggle to generalize across different hardware architectures and noise conditions, motivating the exploration of machine learning approaches for more adaptive and scalable routing strategies.

This study investigates reinforcement learning (RL)-based methods for qubit routing, focusing on how different RL formulations (primitive vs.
hierarchical action spaces) and environment configurations (e.g., lookahead depth, training-circuit sizes) impact routing performance.
The designed RL environment models quantum hardware constraints through coupling graphs and noise parameters, providing configurable state representations and flexible action spaces.

Key findings indicate that a moderate lookahead (e.g., 4 gates) offers the best balance between performance and computational complexity.
Training on circuits with 8–16 gates yields optimal generalization to larger circuits.
Comparing RL policy formulations, hierarchical approaches converge faster and perform robustly on complex topologies, while primitive approaches occasionally achieve higher reliability given sufficient training.
Larger hardware graphs diminish RL’s relative advantage over heuristic transpilers, whereas higher-connectivity topologies improve RL routing efficiency.

Benchmarks against Qiskit’s standard transpilers reveal that RL methods are competitive on small-scale and highly connected devices but face challenges on larger and more constrained architectures.
While RL-based qubit routing can effectively integrate hardware noise and connectivity constraints, scalability and adaptability to dynamic error rates remain open challenges.

Future research should explore integrating more comprehensive noise models, adaptive noise tracking, concurrent gate execution, hybrid heuristic–RL approaches, and benchmarking with real hardware implementations.
As quantum devices scale, RL-driven, noise-aware compilation strategies may become integral to optimizing practical quantum computations.
... Read more

The growing societal demand for privacy, driven by rapid advances in information technologies and machine learning, motivates the development of approaches that reconcile privacy preservation with computational efficiency. This thesis addresses this challenge by bridging two seemingly disparate paradigms: universal blind quantum computation (UBQC), based on measurement-based quantum computation, and quantum machine learning (QML) algorithms such as the Harrow–Hassidim–Lloyd (HHL) algorithm and quantum recommendation systems.

To this end, we developed a transpiler that maps Qiskit quantum circuits into computational brickwork graphs (Graphix Pattern objects), the underlying resource states of UBQC. This enables systematic evaluation of the depth and cost incurred by blind implementations. From these constructions, we established a general upper bound on the depth scaling of the computational graph corresponding to blind algorithms as O(mn), where m is the circuit width and n its original complexity. Building on this framework, we provide detailed analyses of blind implementations of the quantum Fourier transform, HHL, recommendation systems, and quantum transformers.

Finally, the thesis proposes a minimal experimental design for Blind Quantum Machine Learning with resource estimates requiring a total of 750 remotely prepared qubit states, but with only 12 coherent qubits in memory at any time using a conveyor-belt architecture, making the resource requirements compatible with near-term implementations on a quantum internet.
... Read more

Quantum computing holds the potential to solve problems that are intractable for classical systems. However, the physical realization of large-scale quantum systems remains a challenge due to the difficulty of scaling qubit counts. Distributed Quantum Computing (DQC) offers a promising solution by interconnecting multiple Quantum Processing Units (QPUs), effectively increasing the number of usable qubits. This interconnection introduces additional operations and exacerbates the complexity of qubit routing and entanglement management during circuit execution. While a reinforcement learning (RL) approach by Promponas et al. shows promise for qubit routing and EPR management in distributed quantum computing (DQC) environments, it suffers from inconsistent performance and is unable to reliably compile larger circuits. To address these limitations, we introduce a novel action space that allows direct operations between arbitrary qubit pairs, rather than restricting interactions to neighbouring qubits. While this significantly reduces solution depth, it increases the size of the action space, posing scalability challenges. To address this, we propose a novel neural network architecture that computes Q-values for qubit pairs based on the values of their individual qubits, considerably reducing the number of trainable parameters. Additionally, we extend the masking strategy to eliminate sub-optimal actions, effectively constraining the branching factor and accelerating learning. Together, these enhancements enable the agent to compile larger circuits with improved speed and consistency, significantly outperforming the baseline. Overall, our contributions result in better performance and reduced training time, marking a step forward in scalable quantum circuit compilation for distributed quantum systems. ... Read more

The differences between T1 and T2 in real-world quantum computing platforms underscore the importance of studying the thresholds of quantum error-correcting codes under biased noise, also spurring active searches for error-correcting codes with thresholds exceeding the hashing bound under biased noise. Recently, new error-correcting codes such as the XZZX code and the holographic seven-qubit tailored code have exhibited a 50% threshold under pure Pauli noise. Notably, the XZZX code achieves a threshold exceeding the hashing bound in cases of high bias.

This work reports on a holographic quantum error-correcting code, the HaPPY code, which also exhibits a 50% threshold under pure Pauli noise and surpasses the hashing bound threshold under high biased noise. Additionally, this work also explores the threshold of the holographic Steane code under biased noise for comparison.

In addition to studying thresholds under biased noise, this work also investigates the thresholds of various codes, including the Hyper-Invariant Tensor-Network code (HTN code), holographic Reed-Muller code, and some heterogeneous holographic codes, under quantum erasure channels and depolarizing channels.

This work has developed an automated quantum tensor network operator push program, which supports the automated generation of stabilizers and complete logical operators for tensor network quantum error-correcting codes. This greatly enhances the research efficiency of holographic codes, and the program is now ready to be made available to the open-source community. ... Read more

Efficiency in handling instructions within compilation and control processes is essential for scalability and fault-tolerant quantum computation. To mitigate the limited bandwidth for transmission of instructions and energy bottlenecks in cryogenic control architectures, this thesis aims to develop a compressed representation of quantum circuits. To achieve this goal, we study the concepts of algorithmic information theory and resource theory of computation. We focus on description complexity and establish compression as a useful estimate of algorithmic description complexity. With this motivation, we develop a generalized framework for the synthesis of quantum unitaries into a set of native gates and present a Huffman-encoded representation of the instruction stream that has a short code dictionary and offers a 60% compression over binary encoded representations. The developed framework offers 2 major contributions: an energy-efficient encoded representation of the quantum instruction stream and an estimate of the description complexity for quantum circuits. It qualifies as a successful algorithmic approach towards optimizing the QISA and aids the discovery of high-level quantum programming constructs. ... Read more

"Quantum optimal control is a rapidly growing field with diverse methods and applications. In this work, the possibility of using quantum optimal control techniques to co-optimize the energetic cost and the process fidelity of a quantum unitary gate is investigated. The theoretical definition and quantization of quantum unitary gates, as well as the relationship between the process fidelity and the energetic cost of a quantum unitary gate are explored. Two different quantum optimal control methods to co-optimize both fidelity and energetic cost, i.e., the Gradient Ascent Pulse Engineering method and model-free Deep Reinforcement Learning are investigated. The performance of both quantum optimal control techniques in the presence of noise is probed. We find that the energetic cost of a quantum unitary gate can be quantized by integrating the control pulses and norm of the corresponding Hamiltonian operators over the total time duration of the unitary, and for single qubit gates by calculating the arc length of the quantum unitary gate on the Bloch sphere. A Pareto optimal front between the process fidelity and the energetic cost of a quantum gate is identified, where a lower energetic cost yields an inherently lower process fidelity. A python package called ”EUQOC” (Energy Efficient Universal Quantum Optimal Control) has been created to implement energy optimal quantum gate synthesis, both with the Energy Optimal Gradient Ascent Pulse Engineering (EO-GRAPE) method and by model-free Deep Reinforcement Learning. It is found that the EO-GRAPE method performs better than the reinforcement learning methods, for all noise settings and neural network sizes. For future work, the optimization problem could be translated to the frequency domain to increase the computational efficiency. Furthermore, the relationship between information and energy can be investigated by looking at the complexity of the pulse or the decomposition of the quantum unitary gate." ... Read more

Achieving universal and scalable quantum computing with reliably low error rates, despite the presence of unreliable circuit components, requires fault-tolerant quantum error correction. In general, quantum error correction imposes a significant overhead on the computation, motivating exploration of opportunities for optimization. Flag fault tolerance protocols have emerged as important schemes to realize fault tolerance experiments in the near term, because of their low qubit overhead, and absence of strict requirement for elaborate ancillary state preparation, relative to traditional schemes. However, the existing fast-reset, single-flag protocols for small codes generally employ a measurement of all stabilizer generators with unflagged circuits to distinguish a limited set of errors via the syndrome, leading to high circuit depth. In addition, the flagged measurement outcomes play a limited role in differentiating these errors. This motivates the possibility of reducing the circuit depth fault-tolerantly in flag-based syndrome extraction circuits. In this thesis, flag protocols with significantly reduced number of stabilizer measurements are constructed for the [[5,1,3]] code and the Steane code. The new protocols are divided into two classes. In the first class, the reduction is achieved by a dynamic choice of unflagged stabilizer measurements, based on past syndromes, and the utilization of the complete stabilizer group, to distinguish restricted sets of errors signalled by respective flagged measurements. In the second class, the reduction is achieved by measuring three high-weight flagged stabilizers, with the capability to detect a single input error, for the Steane code. The reduced stabilizer sequences are methodically constructed to yield unique and nontrivial syndromes for the relevant error set. This ensures that the fundamental condition of errors being detectable and distinguishable, which is the principal factor for the existing flag protocols to be fault-tolerant, is preserved. Pseudothresholds competitive with the existing flag protocols are established via Monte Carlo simulations under an error model consisting of two-qubit gate depolarizing errors, state preparation errors and measurement errors. Additionally, computer search programs are developed to obtain analogous reduced stabilizer sequences for both classes. These programs are also employed to assist in identifying certain mathematical properties of the high-weight Steane code stabilizers which can detect a single input error: namely, these stabilizers belong to different cosets of the X-stabilizer subgroup, and arise from 8-element subgroups within the stabilizer group. Furthermore, examples of such stabilizer sequences are constructed for few other codes. This thesis highlights the potential of employing parity measurements from the complete stabilizer group and extending beyond conventional adaptive measurements to improve the resource efficiency of fault-tolerant quantum error correction. ... Read more

This thesis presents a novel formulation to study the qubit-mapping problem (QMP). The presented for- mulation redefines the problem in terms of density matrices which represent the quantum algorithm and the underlying architecture—allowing the implementation of techniques from quantum information theory to es- tablish a bounded metric space for comparing these density matrices. The main contribution of this thesis is implementing this formulation in an algorithm to determine the minimal bound on the required number of SWAP operations for a pairing of a quantum algorithm to an underlying device where the initial mapping has been provided. Benchmarks have shown a clear dependence on the β-value. Emphasising the need for future investigations of this dependence to enhance the algorithm’s effectiveness for more extensive algorithms and architectures. While it is essential to acknowledge that the approach may not currently rival the state of the art. ... Read more

The goal of this thesis is to develop a ROS package that facilitates the control and navigation of a Duckiebot robot. With the rise of robot swarms the need for autonomous charging system for robots is increasing. An implementation for decentralised autonomous behaviour for a Duckiebot for a wireless charging system in a Duckietown environment is discussed. The devised system is divided among three different modules and is implemented in ROS:
• An image recognition module;
• A navigation module;
• A motion control module;
The image recognition module uses linear image processing techniques and YOLO object detection in order to detect objects in images from the robots front facing camera. It detects traffic lights and road markings in order to tell the robot where to go.

The navigation module uses odometry to keep track of the robots current position. The odometry is reset in order to maintain accuracy. When the battery of the robot reaches a certain point the robot will decide to
charge. It will then initiate path finding using Lee’s algorithm in order to find a path to a charging park.

Finally the motion control processes all the information in order to drive the wheels of the robot.
The system is thought to be able to navigate to a charging station, charge and then leave the charging station using the designed ROS package. ... Read more

The goal of this thesis is expanding quantum algorithm datasets to enhance our capability to benchmark quantum systems and to open up possibilities for using machine learning techniques in quantum circuit mapping. Both of these areas are currently hindered by the lack of a wide range of useful quantum algorithms. To solve this problem, KetGPT is presented, a model that uses the revolutionary transformer machine learning architecture to generate synthetic, yet realistic looking, quantum circuits. By visual inspection, KetGPT generated circuits are easily distinguishable from random circuits, and show desirable qualities such as structure and human-like programming factors including applying gates in the order of ascending qubits. Consequently, they might be more suitable for certain tasks like benchmarking and training a reinforcement learning compiler. In an attempt to quantify the quality of circuits generated by KetGPT, a separate transformer classifier model was trained on the task of classifying the synthetic circuits generated by KetGPT as either real circuits, or as random circuits. However, although this classifier might capture realistic features of quantum circuits, the classifier has not been unambiguously proven to be reliable, and can therefore not be used as a standalone tool to determine the quality of KetGPT generated quantum circuits. Nevertheless, KetGPT and the transformer classifier are novel, promising approaches in an attempt to expand quantum algorithm datasets. ... Read more

By increasing the step frequency of the runners, it is possible to reduce the risk of injuries due to overload. Techniques like auditory pacing help the athletes to have better control over their step frequency. Nevertheless, synchronizing to a continuous external rhythm costs energy. For this reason, the use of intermittent pacing may be more energy-efficient and more user-friendly for the athlete. We propose using experimental data from previous studies, that analyzed the response of runners to intermittent pacing, to find the most efficient approach for providing the pacing. For this purpose we use reinforcement learning techniques to learn and train our target behavior. This behavior is represented as the target policy and the experimental data is assumed to be sampled using a stochastic sampling policy. However, using only a single batch of initial training data presents a problem due to the continuously increasing difference between the initial sampling policy and the target policy being learned. The use of a batch off-policy algorithm with a standard deviation correction (OPPOSD) presented in (Liu et al., 2019) is then proposed. This algorithm benefits from the advantages of the sampling efficiency characteristic of the off-policy approaches and also introduces a fixing term to tackle the mismatch between the policies. To train and evaluate the learned policies based on the algorithm, a pace behavior simulator was developed from the data of the experiments. A Markov Decision Problem (MDP) was defined on top of the simulator that determines the rules of the pacing environment that the algorithm is set to learn. After translating the experimental data into MDP-like transitions, the OPPOSD algorithm is able to learn a relatively good target policy for the pacing problem. For a future application, the resulting trained model could be deployed for real runners while still having a continuous improvement of the policy in an on-policy or off-policy approach. ... Read more