Instruction scheduling for blind quantum computing

Abstract

Quantum networks offer more capabilities than classical networks. For example, quantum networks can solve certain problems faster than classical networks and they can even solve problems which cannot be solved with classical networks. One well-known quantum network application is blind quantum computing (BQC). In a BQC application a client node sends a computation to a server node in the network. The server node performs this computation without knowing the details about the actual input or computation being performed and returns the result of the computation to the client node. Quantum applications are often repeated many times, due to randomness that is involved in the result of executing a quantum application. When a server node performs BQC repeatedly with multiple client nodes, there follows an interesting problem how all corresponding instructions can be scheduled for the server optimally, given that certain types of instructions referred to as entanglement instructions can only be scheduled at given moments by a so called network schedule. One classical metric used to assess the quality of a schedule is makespan, which is the time that it takes to complete all instructions. A quantum oriented metric involved is success probability, which indicates what fraction of executions yield a desired result when repeatedly executing an application. In this thesis, an experimental demonstration is given of the use of constraint programming (CP) for the scheduling of instructions of quantum network applications. This demonstration focuses on scheduling instructions that the server node should execute when performing BQC repeatedly with a small number of client nodes at the same time. Different CP models are presented that assign start times to tasks that the server node should execute. By comparing the CP models to a baseline scheduler that schedules tasks as soon as possible, it was found that CP can be used to reduce the makespan when BQC is performed by the server node with multiple clients at the same time, while preserving a similar success probability. A main drawback that followed from the CP approach is scalability. Future work is to be done on studying how CP can be used for larger quantum networks.