Optimal mapping of a parallel code's communication graph is increasingly important as both system size and heterogeneity increase. However, the topology-aware task assignment problem is an NP-complete graph isomorphism problem. Existing task scheduling approaches are either heuristic or based on physical optimization algorithms, providing different speed and solution quality tradeoffs. Ising machines such as quantum and digital annealers have recently become available offering an alternative hardware solution to solve certain types of optimization problems. We propose an algorithm that allows expressing the problem for such machines and a domain specific partition strategy that enables to solve larger scale problems. TIGER - topology-aware task assignment mapper tool - implements the proposed algorithm and automatically integrates task - communication graph and an architecture graph into the quantum software environment. We use D-Wave's quantum annealer to demonstrate the solving algorithm and evaluate the proposed tool flow in terms of performance, partition efficiency and solution quality. Results show significant speed-up of the tool flow and reliable solution quality while using TIGER together with the proposed partition.
Optimal mapping of a parallel code's communication graph is increasingly important as both system size and heterogeneity increase. However, the topology-aware task assignment problem is an NP-complete graph isomorphism problem. Existing task scheduling approaches are either heuristic or based on physical optimization algorithms, providing different speed and solution quality tradeoffs. Ising machines such as quantum and digital annealers have recently become available offering an alternative hardware solution to solve certain types of optimization problems. We propose an algorithm that allows expressing the problem for such machines and a domain specific partition strategy that enables to solve larger scale problems. TIGER - topology-aware task assignment mapper tool - implements the proposed algorithm and automatically integrates task - communication graph and an architecture graph into the quantum software environment. We use D-Wave's quantum annealer to demonstrate the solving algorithm and evaluate the proposed tool flow in terms of performance, partition efficiency and solution quality. Results show significant speed-up of the tool flow and reliable solution quality while using TIGER together with the proposed partition.
Optimally mapping a parallel application to compute and communication resources is increasingly important as both system size and heterogeneity increase. A similar mapping problem exists in gate-based quantum computing where the objective is to map tasks to gates in a topology-aware fashion. This is an NP-complete graph isomorphism problem, and existing task assignment approaches are either heuristic or based on physical optimization algorithms, providing different speed and solution quality trade-offs. Ising machines such as quantum and digital annealers have recently become available and offer an alternative hardware solution to solve this type of optimization problems. In this paper, we propose an algorithm that allows solving the topology-aware assignment problem using Ising machines. We demonstrate the algorithm on two use cases, i.e. classical task scheduling and quantum circuit gate scheduling. TIGER---topology-aware task/gate assignment mapper tool---implements our proposed algorithms and automatically integrates them into the quantum software environment. To address the limitations of physical solver, we propose and implement a domain-specific partition strategy that allows solving larger-scale problems and a weight optimization algorithm that allows tuning Ising model parameters to achieve better restuls. We use D-Wave's quantum annealer to demonstrate our algorithm and evaluate the proposed tool flow in terms of performance, partition efficiency, and solution quality. Results show significant speed-up compared to classical solutions, better scalability, and higher solution quality when using TIGER together with the proposed partition method. It reduces the data movement cost by 68\% in average for quantum circuit assignment compared to the IBM QX optimizer.
To overcome the physical limitations of scaling monolithic quantum computers, distributed quantum computing (DQC) interconnects multiple smaller-scale quantum processing units (QPUs) to form a quantum network. However, this approach introduces a critical challenge, namely the high cost of quantum communication between remote QPUs incurred by quantum state teleportation and quantum gate teleportation. To minimize this communication overhead, DQC compilers must strategically partition quantum circuits by mapping logical qubits to distributed physical QPUs. Static graph partitioning methods are fundamentally ill-equipped for this task as they ignore execution dynamics and underlying network topology, while metaheuristics require substantial computational runtime. In this work, we propose a heuristic based on beam search to solve the circuit partitioning problem. Our time-aware algorithm incrementally constructs a low-cost sequence of qubit assignments across successive time steps to minimize overall communication overhead. The time and space complexities of the proposed algorithm scale quadratically with the number of qubits and linearly with circuit depth, offering a significant computational speedup over common metaheuristics. We demonstrate that our proposed algorithm consistently achieves significantly lower communication costs than static baselines across varying circuit sizes, depths, and network topologies, providing an efficient compilation tool for near-term distributed quantum hardware.
The emerging paradigm of distributed quantum computing promises a potential solution to scaling quantum computing to currently unfeasible dimensions. While this approach itself is still in its infancy, and many obstacles must still be overcome before its physical implementation, challenges from the software and algorithmic side must also be identified and addressed. For instance, this paradigm shift requires a new form of compiler that considers the network constraints in general as well as phenomena arising due to the nature of quantum communication. In distributed quantum computing, large circuits are divided into smaller subcircuits such that they can be executed individually and simultaneously on multiple QPUs that are connected through quantum channels. As quantum communication, for example, in the form of teleportation, is expensive, it must be used sparingly. We address the problem of assigning qubits to QPUs to minimize communication costs in two different ways. First by applying time-aware algorithms that take into account the changing connectivity of a given circuit as well as the underlying network topology. We define the optimization problem, use simulated annealing and an evolutionary algorithm and compare the results to graph partitioning and sequential qubit assignment baselines. In another approach, we propose an evolutionary-based quantum circuit optimization algorithm that adjusts the circuit itself rather than the schedule to reduce the overall communication cost. We evaluate the techniques against random circuits and different network topologies. Both evolutionary algorithms outperform the baseline in terms of communication cost reduction. We give an outlook on how the approaches can be integrated into a compilation framework for distributed quantum computing.
Accurately solving discrete optimization problems is still a serious challenge for classical computing systems. Despite significant progress, it is still impossible to optimally solve examples of the size found in real-world applications. This article examines the problem of scheduling tasks on one machine. Each task has an associated execution time, desired completion date, and a late penalty feature weight. The order of executing tasks should be determined in a manner that minimizes the sum of delay costs. Despite the simplicity of the formulation, this problem is NP-hard and is representative of optimization challenges encountered in the practice of production control, management, and logistics.In this work, we propose using a quantum computing environment to solve it. The main disadvantage of calculations on quantum computers is their nondeterminism. Therefore, there is no guarantee of optimality of solutions to discrete optimization problems determined on a quantum computer.We propose a novel approach to constructing hybrid algorithms that guarantee the optimality of the solution. The algorithm for solving the task scheduling problem considered here is based on the branch and bound method. Calculations are performed alternately on a classical computer and a quantum computer. The lower and upper bounds of the criterion function are determined on a quantum computer. Computational experiments were performed on the D-Wave quantum computer. In small examples, the algorithm runs faster and generates significantly fewer solution tree vertices than its counterpart running on a classic computer. For larger examples, the proposed runtime-constrained method, acting as a heuristic, is an interesting alternative to using quantum computing hardware in relation to classical approaches based on silicon computers.
Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.
The qubit-mapping problem aims to assign and route qubits of a quantum circuit onto an noisy intermediate-scale quantum (NISQ) device in an optimized fashion, with respect to some cost function. Finding an optimal solution to this problem is known to scale exponentially in computational complexity; as such, it is imperative to investigate scalable qubit-mapping solutions for NISQ computation. In this work, a noise-aware heuristic qubit-assignment algorithm (which assigns initial placements for qubits in a quantum algorithm to qubits on an NISQ device, but does not route qubits during the quantum algorithm’s execution) is presented and compared against the optimalbrute-forcesolution, as well as a trivial qubit assignment, with the aim to quantify the performance of our heuristic qubit-assignment algorithm. We find that for small, connected-graph algorithms, our heuristic-assignment algorithm faithfully lies in between the effective upper and lower bounds given by the brute-force and trivial qubit-assignment algorithms. Additionally, we find that the topological-graph properties of quantum algorithms with over six qubits play an important role in our heuristic qubit-assignment algorithm’s performance on NISQ devices. Finally, we investigate the scaling properties of our heuristic algorithm for quantum processors with up to 100 qubits; here, the algorithm was found to be scalable for quantum-algorithms that admit path-like graphs. Our findings show that as the size of the quantum processor in our simulation grows, so do the benefits from utilizing the heuristic qubit-assignment algorithm, under particular constraints for our heuristic algorithm. This work, thus, characterizes the performance of a heuristic qubit-assignment algorithm with respect to the topological-graph and scaling properties of a quantum algorithm that one may wish to run on a given NISQ device.