Instruction scheduling is a key transformation in backend compilers that take an untimed description of an algorithm and assigns time slots to the algorithm's instructions so that they can be executed as efficiently as possible while taking into account the target processor limitations, such as the amount of computational units available. For example, for a superconducting quantum processor these restrictions include the amount of analogue instruments available to play the waveforms to drive the qubit rotations or on-chip connectivity between qubits. Current small-scale quantum processors contain only a few qubits; therefore, it is feasible to drive qubits individually albeit not scalable. Consequently, for NISQ and beyond NISQ devices, it is expected that classical instrument sharing to be designed in the future quantum control architectures where several qubits are connected to an instrument and multiplexing is used to activate only the qubits performing the same quantum operation at a time. Existing quantum scheduling algorithms either rely on ILP formulations, which do not scale well, or use heuristic based algorithms such as list scheduling which are not versatile enough to deal with quantum requirements such as scheduling with exact relative timing constraints between instructions, situation that might occur when decomposing complex instructions into native ones and requiring to keep a fixed timing between the primitive ones to guarantee correctness. In this paper, we propose a novel resource constrained scheduling algorithm that is based on the SDC formulation, which is the state-of-the-art algorithm used in the reconfigurable computing. We evaluate it against a list scheduler and describe the benefits of the proposed approach. We find that the SDC-based scheduling is not only able to find better schedules but also model flexible relative timing constraints.
Instruction scheduling is a key transformation in backend compilers that take an untimed description of an algorithm and assigns time slots to the algorithm's instructions so that they can be executed as efficiently as possible while taking into account the target processor limitations, such as the amount of computational units available. For example, for a superconducting quantum processor these restrictions include the amount of analogue instruments available to play the waveforms to drive the qubit rotations or on-chip connectivity between qubits. Current small-scale quantum processors contain only a few qubits; therefore, it is feasible to drive qubits individually albeit not scalable. Consequently, for NISQ and beyond NISQ devices, it is expected that classical instrument sharing to be designed in the future quantum control architectures where several qubits are connected to an instrument and multiplexing is used to activate only the qubits performing the same quantum operation at a time. Existing quantum scheduling algorithms either rely on ILP formulations, which do not scale well, or use heuristic based algorithms such as list scheduling which are not versatile enough to deal with quantum requirements such as scheduling with exact relative timing constraints between instructions, situation that might occur when decomposing complex instructions into native ones and requiring to keep a fixed timing between the primitive ones to guarantee correctness. In this paper, we propose a novel resource constrained scheduling algorithm that is based on the SDC formulation, which is the state-of-the-art algorithm used in the reconfigurable computing. We evaluate it against a list scheduler and describe the benefits of the proposed approach. We find that the SDC-based scheduling is not only able to find better schedules but also model flexible relative timing constraints.
Execution of quantum algorithms requires a quantum computer architecture with a dedicated quantum instruction set that is capable of supporting translation of workloads into actual quantum operations acting on the qubits. State-of-the-art qubit control setups typically utilize general purpose test instruments such as arbitrary waveform generators (AWGs) to generate a limited set of waveforms or pulses. These waveforms are precomputed and stored prior to execution, and then used to produce control pulses during execution. Besides their prohibitive cost and limited scalability, such instruments suffer from poor programmability due to the absence of an instruction set architecture (ISA). Limited memory for pulse storage ultimately determines the total number of supported quantum operations. In this work, we present a scalable qubit control system that enables efficient qubit control using a flexible ISA to drive a direct digital synthesis (DDS) pipeline producing nanosecond-accurate qubit control signals dynamically. The designed qubit controller provides a higher density of control channels, a scalable design, better programmability, and lower cost compared to state-of-the-art systems. In this work, we discuss the new qubit controller's capabilities, its architecture and instruction set, and present experimental results for coherent qubit control.
The advent of quantum computing promises transformative advancements across various scientific and technological domains. However, realizing this potential hinges critically on the efficient execution of quantum algorithms. A significant hurdle lies in the intricate orchestration of quantum resources – qubits, coherence times, and gate fidelity – to meet the demanding requirements of complex quantum algorithms. Traditional scheduling methods often fail to adequately account for these constraints, leading to suboptimal performance and increased execution times. This paper proposes a novel approach to quantum algorithm scheduling by formulating the problem as a Constraint Programming (CP) model. This approach leverages the power of CP solvers to systematically explore the solution space, identifying schedules that maximize resource utilization while adhering to stringent hardware limitations. We introduce a framework for representing quantum algorithms and their associated constraints within a CP environment, enabling automated optimization. The core of the method involves defining constraints related to qubit connectivity, coherence time limitations, and gate fidelity errors. The resulting CP model is then solved using state-of-the-art CP solvers, producing optimized schedules that demonstrate significant improvements in resource efficiency compared to naive scheduling strategies. This work represents a substantial advance in quantum algorithm scheduling, offering a robust and scalable solution for harnessing the full power of quantum hardware.
Quantum algorithms need to be compiled to respect the constraints imposed by quantum processors, which is known as the mapping problem. The mapping procedure will result in an increase of the number of gates and of the circuit latency, decreasing the algorithm’s success rate. It is crucial to minimize mapping overhead, especially for noisy intermediate-scale quantum (NISQ) processors that have relatively short qubit coherence times and high gate error rates. Most of prior mapping algorithms have only considered constraints, such as the primitive gate set and qubit connectivity, but the actual gate duration and the restrictions imposed by the use of shared classical control electronics have not been taken into account. In this article, we present a mapper called Qmap to make quantum circuits executable on scalable processors with the objective of achieving the shortest circuit latency. In particular, we propose an approach to formulate the classical control restrictions as resource constraints in a conventional list scheduler with polynomial complexity. Furthermore, we implement a routing heuristic to cope with the connectivity limitation. This router finds a set of movement operations that minimally extends circuit latency. To analyze the mapping overhead and evaluate the performance of different mappers, we map 56 quantum benchmarks onto a superconducting processor named Surface-17. Compared to a prior mapping strategy that minimizes the number of operations, Qmap can reduce the latency overhead (LtyOH) up to 47.3% and operation overhead up to 28.6%, respectively.
Proposing an architecture that effectively compensates for physical hardware inefficiencies through redundant resources is a key challenge in quantum computer design. Although the representation of quantum systems is currently limited to tens of qubits, scaling existing small scale laboratory systems into large scale quantum computers capable of solving meaningful practical problems remains a primary research objective. Focusing on this issue, this paper proposes a scalable architecture for quantum information processors. Physical design, one of the two main processes in quantum computer design, transforms a circuit netlist into a technology specific layout. Quantum mapping comprising partitioning, placement, scheduling, and routing is an essential part of this process, and these stages are inherently interdependent. In this research, considering the dependencies between these stages, we present an Integer Linear Programming (ILP) model for qubit partitioning and placement, determining the optimal module and physical location for each qubit. Furthermore, we propose a heuristic approach for the placement and scheduling of quantum operators on a scalable, modular, universal ion trap quantum computer (MUSIQC), aiming to minimize circuit execution delay. Qubit routing is performed using a greedy strategy. For evaluation, the proposed method was applied to both Ripple-Carry Adder and Carry-Lookahead Adder circuits. Experimental results demonstrate that the proposed approach reduces the average circuit delay by approximately 58.98% for Ripple-Carry Adder circuits and 33% for Carry-Lookahead Adder circuits compared to the best existing method. These results underscore the effectiveness of our integrated framework, where ILP-based partitioning optimizes for dominant operational costs, while our subsequent resource-aware scheduler actively manages parallelism and contention to achieve the minimal overall circuit execution delay.
Efforts to build quantum computers using ion-traps have demonstrated all elementary qubit operations necessary for scalable implementation. Modular architectures have been proposed to construct modest size quantum computers with up to 104- 106qubits using technologies that are available today (MUSIQC architecture). Concrete scheduling procedure to execute a given quantum algorithm on such a hardware is a significant task, but existing quantum CAD tools generally do not account for the underlying connectivity of the qubits or the limitation on the hardware resources available for the scheduling. We present a scheduler and performance simulator that fully accounts for these resource constraints, capable of estimating the execution time and error performances of executing a quantum circuit on the hardware. We outline the construction of tool components, and describe the process of mapping the qubits to ions and scheduling the physical gates in the MUSIQC architecture. Using this tool, we quantify the trade-off between hardware resource constraints and performance of the computer and show that at an expense of x fold increase in latency, a minimum of 1.6x resource reduction is possible for executing a three-qubit Bernstein-Vazirani algorithm encoded using Steane code.
Quantum algorithms can be efficiently emulated on classical hardware such as field programmable gate arrays (FPGAs), achieving significant speedup over software simulations. However, the increase in the required hardware resources for emulating quantum systems becomes a critical limitation as the number of qubits is increased. In this paper, we propose a scalable emulation framework for modeling quantum algorithms on FPGAs that employs efficient resource scheduling such as space and space-time scheduling. In addition, full floating point precision arithmetic and dataflow non-linear (dynamic) pipelining are also used to achieve higher accuracy and higher throughput. We propose scalable and optimized hardware architectures for Quantum Fourier Transform (QFT) and Grover's search algorithm and demonstrate the scalability of our framework by scaling the system up to 5 fully-entangled qubits. A multi-node (multi-FPGA), state-of-the-art high-performance reconfigurable computer (HPRC) was used for implementation of the proposed architectures. Our experimental results show that by employing efficient resource scheduling techniques, the hardware resource constraints could be mitigated and the proposed emulation framework could be made feasible for emulation of more complex, larger-scale quantum algorithms while maintaining higher accuracy and throughput than existing work.