Method of operating a quantum information processing system

Abstract

A method of operating a quantum information processing system. The quantum information processing system includes an array of connected qubits. The method of operating the quantum information processing system uses a linear network coding solution to performing an operation between the quantum states of two or more qubits of the array.

Claims

1. A method of operating a quantum information processing system, wherein the quantum information processing system comprises an array of a plurality of qubits and a plurality of connections between the plurality of qubits in the array, wherein the plurality of qubits in the array and the plurality of connections between the plurality of qubits are arranged such that at least two of the qubits in the array do not have a direct connection therebetween; wherein the method of operating the quantum information processing system comprises: for a linear network coding solution for performing an operation or operations between the quantum states of two or more qubits of the plurality of qubits; wherein the linear network coding solution is based on a network of a plurality of nodes corresponding to the plurality of qubits and a plurality of edges between the nodes corresponding to the plurality of connections between the qubits; and wherein each of the plurality of edges comprises a direction from one of the plurality of nodes to another of the plurality of nodes, such that the plurality of nodes comprise: one or more transmitter nodes that are connected to only one or more outgoing edges of the plurality of edges, each of the one or more outgoing edges having a direction towards another node; one or more receiver nodes that are connected to only one or more incoming edges of the plurality of edges, each of the one or more incoming edges having a direction from another node; and one or more relay nodes that are each connected to at least an outgoing edge having a direction towards another node and to at least an incoming edge having a direction from another node: determining a time ordering of the plurality of nodes of the network for operating on the plurality of qubits, the time ordering of the plurality of nodes comprising a group of a plurality of initial nodes that are first in the time ordering of the plurality of nodes, one or more groups each of a plurality of intermediate nodes that are intermediate in the time ordering of the plurality of nodes, and a group of a plurality of final nodes that are last in the time ordering of the plurality of nodes; determining a time ordering of the plurality of edges of the network for operating between the plurality of qubits, wherein the time ordering is determined for the plurality of outgoing edges for the nodes in each of the groups of nodes in the time ordering of the plurality of nodes; initialising the state of each of the plurality of qubits; for the transmitter and relay nodes of the group of the plurality of initial nodes: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the transmitter and relay nodes of each of the groups of the plurality of intermediate nodes, processed in the time ordering of the intermediate groups: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the relay nodes of the group of the plurality of intermediate nodes that have an incoming edge from a node of a group of nodes having an earlier time ordering, realising a measurement of the quantum states of the qubits corresponding to those relay nodes of the group of the plurality of intermediate nodes; and for the relay nodes of the group of the plurality of intermediate nodes that have an incoming edge from a node of a group of nodes having a later time ordering, for each of the outgoing edges from these relay nodes in order of the time ordering of the plurality of edges, performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the transmitter and relay nodes of the group of the plurality of final nodes: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for all of the relay nodes of the plurality of nodes, realising a measurement of the quantum states of the qubits corresponding to the relay nodes; and for all of the receiver nodes of the plurality of nodes, performing an operation on the quantum states of the qubits corresponding to the receiver nodes.

2. The method as claimed in claim 1, wherein the array of qubits and the network of nodes are arranged such that the pairs of qubits of the array that can interact are restricted to the corresponding pairs of the network that are connected by edges of the network.

3. The method as claimed in claim 1, wherein the overall operation to be performed comprises an operation between multiple pairs of qubits that are remote from each other in the array, and the individual operations comprise a plurality of quantum entanglement operations on the quantum states of a plurality of different pairs of qubits in the array.

4. The method as claimed in claim 1, wherein the qubits of the array of qubits are arranged such that a plurality of single-qubit operations acting on a plurality of different single qubits may be performed in parallel, and such that a plurality of CNOT operations acting on non-intersecting pairs of qubits.

5. The method as claimed in claim 1, wherein the quantum information processing comprises a control system for determining the operations to perform on the qubits based on the linear network coding solution, wherein the control system is arranged such that the classical information is not restricted to the network of the quantum information processing system.

6. The method as claimed in claim 1, wherein the time ordering of the plurality of nodes is determined such that two nodes may share the same integer under the time ordering, only if they are not adjacent in the network.

7. The method as claimed in claim 1, wherein the time ordering of the plurality of edges of the network is determined such that two edges that have a common relationship to a node do not have the same position according to the time ordering.

8. The method as claimed in claim 1, wherein the qubits which are at nodes that are not the sources of any directed edges are initialised to the quantum state |0, the qubits which are at nodes that have an incoming edge from a node having an earlier time ordering are initialised to the quantum state |0, and the remainder of the qubits are initialised to the quantum state |+.

9. The method as claimed in claim 1, wherein for each qubit for which the measurement outcome is |−, a termination subroutine comprises performing Z corrections on one or more of the other qubits of the array, such that the post-measurement state of the qubit is that which would have been realised if the measurement outcome had instead been |+.

10. The method as claimed in claim 9, wherein the method comprises classically simulating the process of distributing entanglement across the array of the plurality qubits to determine the Z corrections to perform on one or more of the other qubits of the array.

11. The method as claimed in claim 10, wherein the qubits are initialised to the state |0 or to the state |+, wherein for k qubits initialised to the state |+ that are labelled q.sub.1, q.sub.2, . . . , q.sub.k, wherein to classically simulate the process of distributing entanglement across the array of the plurality qubits, the initial state of the n qubits of the array of qubits is represented by an array C and a column p, each of which has a number of rows which is one more than the number of qubits k initialised to the state |+, wherein the columns of C are indexed by integers 0, 1, 2, . . . , n, and the rows of both C and p by integers 0, 1, 2, . . . , k, wherein column 0 of C initially has entries comprising a 1 in row 0, and 0 in all other rows; and wherein for a Pauli X operation on a qubit with index j, the termination subroutine comprises toggling the value of the entry in column j, row 0 of the array C between 0 and 1.

12. The method as claimed in claim 10, wherein the qubits are initialised to the state |0 or to the state |+, wherein for k qubits initialised to the state |+ that are labelled q.sub.1, q.sub.2, . . . , q.sub.k, wherein to classically simulate the process of distributing entanglement across the array of the plurality qubits, the initial state of the n qubits of the array of qubits is represented by an array C and a column p, each of which has a number of rows which is one more than the number of qubits k initialised to the state |+, wherein the columns of C are indexed by integers 0, 1, 2, . . . , n, and the rows of both C and p by integers 0, 1, 2, . . . , k, wherein column 0 of C initially has entries comprising a 1 in row 0, and 0 in all other rows; and wherein for a Pauli Z operation on a qubit with index j, the termination subroutine comprises, for each row r in which the entry in column j of C is equal to 1, toggling the value of the entry in row r of p between 0 and 1.

13. The method as claimed in claim 10, wherein the qubits are initialised to the state |0 or to the state |+, wherein to classically simulating the process of distributing entanglement across the array of the plurality qubits, the initial state of the n qubits of the array of qubits is represented by an array C and a column p, each of which has a number of rows which is one more than the number of qubits k initialised to the state |+, wherein the k qubits that are initialised to the state |+ are labelled q.sub.1, q.sub.2, . . . , q.sub.k, wherein the columns of C are indexed by integers 0, 1, 2, . . . , n, and the rows of both C and p by integers 0, 1, 2, . . . , k, wherein column 0 of C initially has entries comprising a 1 in row 0, and 0 in all other rows; and wherein for a CNOT operation whose control is a qubit with index h and whose target is a qubit with index j, the termination subroutine comprises, for each row r in which the entry in column h of C is equal to 1, toggling the entry in row r of column h of C between 0 and 1.

14. The method as claimed in claim 10, wherein the qubits are initialised to the state |0 or to the state |+, wherein to classically simulating the process of distributing entanglement across the array of the plurality qubits, the initial state of the n qubits of the array of qubits is represented by an array C and a column p, each of which has a number of rows which is one more than the number of qubits k initialised to the state |+, wherein the k qubits that are initialised to the state |+ are labelled q.sub.1, q.sub.2, . . . , q.sub.k, wherein the columns of C are indexed by integers 0, 1, 2, . . . , n, and the rows of both C and p by integers 0, 1, 2, . . . , k, wherein column 0 of C initially has entries comprising a 1 in row 0, and 0 in all other rows; and wherein for a measurement in either the |0, |1 basis or the |+, |− basis on a qubit with index j, the termination subroutine comprises computing an equivalent representation of the pre-measurement state, transforming the array C and the column p, as follows: defining an array D, comprising C with an extra column comprising the entries of p, putting D into a row echelon form, in which column j is either a pivot column, zero, or equal to column 0, and having put D in row echelon form, taking the final column of D as a revised value of p, and the remaining columns as a revised value of C.

15. The method as claimed in claim 14, wherein for a measurement in the |+, |− basis on a qubit with index j: if column j of C has a single 1 in some row r>1, and row r has only the single 1 entry in column j, the termination subroutine comprises making no change to C or to the column p and taking the measurement outcome to be |+ if the entry in row r of p is equal to 0, and |− otherwise; if column j of C has a single 1 in some row r>1, but row r has more than one entry which is 1, or if column j of C has no 1 entries in any row r>1, the termination subroutine comprises adding a new row to the bottom of C and of p with index k+1, with entries all 0, and selecting a measurement outcome y to represent the measurement outcome, where y=0 denotes a |+ outcome and y=1 denotes |− outcome, and toggling the entry in row k+1 of column j and in row k+1 of p when y=1, and if column j has any other entries of 1 in a row 0<r<k+1, toggling the entry in row r of column j and in row r of p when y=1.

16. The method as claimed in claim 14, wherein for a measurement in the |0 , |1 basis on a qubit with index j: if column j of C is entirely 0 or equal to column 0 of C, the termination subroutine comprises making no change to C or to the column p and taking the measurement outcome to be the entry in row 0 of column j of C; if column j of C has a single 1 in row r>1, selecting a measurement outcome y to represent the measurement outcome, and if y is equal to 1, toggling the entry in row 0 of any column h in which the entry in row r is equal to 1, toggling the entry in row 0 of p if the entry in row r is equal to 1, and removing the row r from C and from p, re-indexing all rows numbered higher than r.

17. The method as claimed in claim 1, the method further comprising performing a delayed signal correction on the nodes of the network, wherein the delayed signal correction substitutes transmission of correlations by CNOT operations on the array of qubits, with transmission of classical correlations on the nodes of the network.

18. A quantum information processing system for performing an operation or operations between the quantum states of two or more qubits of a plurality of qubits of the quantum information processing system, wherein the quantum information processing system comprises: an array of a plurality of qubits and a plurality of connections between the plurality of qubits in the array, wherein the plurality of qubits in the array and the plurality of connections between the plurality of qubits are arranged such that at least two of the qubits in the array do not have a direct connection therebetween; wherein the quantum information processing system is configured to: for a linear network coding solution for performing an operation or operations between the quantum states of two or more qubits of the plurality of qubits; wherein the linear network coding solution is based on a network of a plurality of nodes corresponding to the plurality of qubits and a plurality of edges between the nodes corresponding to the plurality of connections between the qubits; and wherein each of the plurality of edges comprises a direction from one of the plurality of nodes to another of the plurality of nodes, such that the plurality of nodes comprise: one or more transmitter nodes that are connected to only one or more outgoing edges of the plurality of edges, each of the one or more outgoing edges having a direction towards another node; one or more receiver nodes that are connected to only one or more incoming edges of the plurality of edges, each of the one or more incoming edges having a direction from another node; and one or more relay nodes that are each connected to at least an outgoing edge having a direction towards another node and to at least an incoming edge having a direction from another node: determine a time ordering of the plurality of nodes of the network for operating on the plurality of qubits, the time ordering of the plurality of nodes comprising a group of a plurality of initial nodes that are first in the time ordering of the plurality of nodes, one or more groups each of a plurality of intermediate nodes that are intermediate in the time ordering of the plurality of nodes, and a group of a plurality of final nodes that are last in the time ordering of the plurality of nodes; determine a time ordering of the plurality of edges of the network for operating between the plurality of qubits, wherein the time ordering is determined for the plurality of outgoing edges for the nodes in each of the groups of nodes in the time ordering of the plurality of nodes; initialise the state of each of the plurality of qubits; for the transmitter and relay nodes of the group of the plurality of initial nodes: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: perform an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the transmitter and relay nodes of each of the groups of the plurality of intermediate nodes, processed in the time ordering of the intermediate groups: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: perform an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the relay nodes of the group of the plurality of intermediate nodes that have an incoming edge from a node of a group of nodes having an earlier time ordering, realise or simulate a measurement of the quantum states of the qubits corresponding to those relay nodes of the group of the plurality of intermediate nodes; and for the relay nodes of the group of the plurality of intermediate nodes that have an incoming edge from a node of a group of nodes having a later time ordering, for each of the outgoing edges from these relay nodes in order of the time ordering of the plurality of edges, perform an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the transmitter and relay nodes of the group of the plurality of final nodes: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: perform an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for all of the relay nodes of the plurality of nodes, realise or simulate a measurement of the quantum states of the qubits corresponding to the relay nodes; and for all of the receiver nodes of the plurality of nodes, perform an operation on the quantum states of the qubits corresponding to the receiver nodes.

19. A non-transitory computer readable storage medium storing computer software code which when executing on a quantum information processing system performs a method of operating a quantum information processing system, wherein the quantum information processing system comprises an array of a plurality of qubits and a plurality of connections between the plurality of qubits in the array, wherein the plurality of qubits in the array and the plurality of connections between the plurality of qubits are arranged such that at least two of the qubits in the array do not have a direct connection therebetween; wherein the method of operating the quantum information processing system comprises: for a linear network coding solution for performing an operation or operations between the quantum states of two or more qubits of the plurality of qubits; wherein the linear network coding solution is based on a network of a plurality of nodes corresponding to the plurality of qubits and a plurality of edges between the nodes corresponding to the plurality of connections between the qubits; and wherein each of the plurality of edges comprises a direction from one of the plurality of nodes to another of the plurality of nodes, such that the plurality of nodes comprise: one or more transmitter nodes that are connected to only one or more outgoing edges of the plurality of edges, each of the one or more outgoing edges having a direction towards another node; one or more receiver nodes that are connected to only one or more incoming edges of the plurality of edges, each of the one or more incoming edges having a direction from another node; and one or more relay nodes that are each connected to at least an outgoing edge having a direction towards another node and to at least an incoming edge having a direction from another node: determining a time ordering of the plurality of nodes of the network for operating on the plurality of qubits, the time ordering of the plurality of nodes comprising a group of a plurality of initial nodes that are first in the time ordering of the plurality of nodes, one or more groups each of a plurality of intermediate nodes that are intermediate in the time ordering of the plurality of nodes, and a group of a plurality of final nodes that are last in the time ordering of the plurality of nodes; determining a time ordering of the plurality of edges of the network for operating between the plurality of qubits, wherein the time ordering is determined for the plurality of outgoing edges for the nodes in each of the groups of nodes in the time ordering of the plurality of nodes; initialising the state of each of the plurality of qubits; for the transmitter and relay nodes of the group of the plurality of initial nodes: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the transmitter and relay nodes of each of the groups of the plurality of intermediate nodes, processed in the time ordering of the intermediate groups: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the relay nodes of the group of the plurality of intermediate nodes that have an incoming edge from a node of a group of nodes having an earlier time ordering, realising a measurement of the quantum states of the qubits corresponding to those relay nodes of the group of the plurality of intermediate nodes; and for the relay nodes of the group of the plurality of intermediate nodes that have an incoming edge from a node of a group of nodes having a later time ordering, for each of the outgoing edges from these relay nodes in order of the time ordering of the plurality of edges, performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for the transmitter and relay nodes of the group of the plurality of final nodes: for each of the outgoing edges from these transmitter and relay nodes in order of the time ordering of the plurality of edges: performing an operation between the quantum states of the pair of qubits that are connected by the connection corresponding to the outgoing edge; for all of the relay nodes of the plurality of nodes, realising a measurement of the quantum states of the qubits corresponding to the relay nodes; and for all of the receiver nodes of the plurality of nodes, performing an operation on the quantum states of the qubits corresponding to the receiver nodes.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) An embodiment of the invention will now be described, by way of example only, with reference to the accompanying drawings in which:

(2) FIG. 1 shows a quantum information processing system according to an embodiment of the present invention;

(3) FIG. 2 shows a network of nodes according to an embodiment of the present invention;

(4) FIG. 3 shows a classical linear network coding solution for the network shown in FIG. 2;

(5) FIG. 4 shows a scheduling derived for the network shown in FIG. 2;

(6) FIG. 5 shows a time-coding derived for the network shown in FIG. 2; and

(7) FIGS. 6 to 21 show the steps of a method of operating a quantum information processing system, using the network of FIG. 2, according to an embodiment of the present invention.

DETAILED DESCRIPTION

(8) Quantum information processing systems exploit quantum mechanical phenomena such as superposition and entanglement to perform data processing calculations. In order to provide a large scale system, capable of performing useful calculations, a network of multiple qubits need to be provided. This brings the challenge of performing calculations between qubits that may be remote from each other, which is often prevented by quantum decoherence. Embodiments of the present invention that seek to provide improved methods for quantum information processing will now be described.

(9) Entanglement is a form of quantum correlation that is useable in many different ways in quantum information processing. In particular, for two qubits A and B which are distant from one another, it is possible to perform a two-qubit operation between A and B, if there is a qubit A′ which is near to A and a qubit B′ which is near to B, which that A′ and B′ share entanglement, and if it is possible to perform two qubit operations directly between A and A′ and between B and B′, and if the classical information of measurement outcomes on A′ and B′ can be transmitted quickly to either A or B. In this way, the entanglement between two systems close together can be exploited to extend entanglement interactions across a network to mediate an interaction between two remote systems in the network. In turn, for a network of multiple systems (e.g. qubits), this allows information to be distributed over the network while maintaining quantum coherence.

(10) Embodiments of the present invention provide a method of distributing entanglement concurrently between many pairs of systems (A.sub.1,B.sub.1), (A.sub.2,B.sub.2), . . . (A.sub.m,B.sub.m) for some integer m>1, where the systems A.sub.j and B.sub.j each store a single qubit of quantum information. Furthermore, the network of the systems is such that (owing to the particular quantum hardware of the qubit systems) there are restrictions on which pairs of systems are able to interact directly with each other. This prevents remote systems in the network interacting directly, for example. Such interactions must be mediated between intermediate qubit systems.

(11) More generally, embodiments of the present invention provide a scheme of generating entanglement procedures for the qubit systems of the network from an input specification comprising a “linear network coding solution”.

(12) Embodiments take, as an input, a description of a linear network coding solution. A linear network coding solution is a communications protocol for disseminating “classical” (conventional, non-quantum) information through a network. In the present embodiments, such a linear network coding solution comprises a list of nodes in the network which are “transmitters”, a list of nodes which are “receivers” and a list of “relay” nodes. The nodes of the linear network coding solution, taken as this input, correspond to the different systems (qubits) in the hardware platform (network).

(13) The linear network coding solution describes how certain information may be transmitted collectively from the transmitters to the receivers, by a schedule of one-way communication acts from nodes to other nodes which are adjacent in the network. Each communication act comprises one node sending a message to one other node. The messages are each a single bit, which may be either 0 or 1.

(14) The method according to embodiments of the present invention requires a description of such a linear network coding solution, in which: every node is involved in at most one communication act with any other given node; the nodes which are “transmitters” are those nodes which only send outgoing messages; the nodes which are “receivers” are those nodes which only receive incoming messages; the nodes which are “relays” are those nodes which both receive incoming messages and send outgoing messages; the communications acts are ordered so that no node receives an incoming message after it has sent an outgoing message; the outgoing messages which are sent by each relay node r, are computed as the sum modulo 2 (i.e. the parity) of all of the incoming messages to the node r.

(15) A “directed edge” of the network refers to a pair of nodes that are involved in a communications act, where the node which sends a message in that communications act is called the “source” and the node which receives the message is called the “target”. Thus, a node may be referred to as an “outgoing edge” for a directed edge for which the node is a source; and node may be referred to as an “incoming edge” for a directed edge for which the node is a target.

(16) The linear network coding solution is supplemented with a “time-coding” of the directed edges. This assigns to each directed edge a time-code ranging over integers 1, 2, . . . up to (and including) some limit “B” that is greater than 1. Of these time-codes, any pair of directed edges that have the same time-code do not have either the same source node or the same target node. A time-coding which satisfies this requirement is called “conflict-free”. There are ways to verify whether a time-code is conflict free, and ways to produce such a conflict-free time-coding of the messages, both of which are known to the skilled person.

(17) Separately from the linear network coding solution and the time-coding, the method according to embodiments of the present invention also uses a proposed “schedule” of the nodes. This schedule assigns time-slots to each node, where the time-slots are represented by integers 1, 2, . . . up to (and including) some limit “A” which is greater than 1. Two nodes may share the same integer under the schedule, only if they are not adjacent in the network. There are ways to produce such a schedule that are known to the skilled person. One node is described as being scheduled “earlier” than another if the integer “j” assigned to the former is less than the integer “k” assigned to the latter.

(18) The method according to embodiments of the present invention provides a way to “compile” a sequence of quantum operations (e.g. represented as a set of instructions in a quantum programming language) from the input described above. The operations may be suitable for any hardware platform that has multiple qubits (e.g. network of qubits), where: the nodes of the network taken as the input correspond to qubits in the hardware platform, with directed edges in the network only between nodes that correspond to pairs of qubits, where a CNOT operation can be realised with the control qubit corresponding to the source node and the target qubit corresponding to the target node; it is possible to realise certain unitary transformations (X and Z Pauli rotations) and measurements (in the |0, |1 basis and in the |+, |− basis) on the qubits; and single-qubit operations acting on different qubits may be performed in parallel, and CNOT operations on non-intersecting pairs of qubits may also be performed in parallel.

(19) The hardware platform includes a control system that determines the operations to perform on each qubit. The control system can perform parity computations and has a low latency of processing this information relative to the time required to realise qubit measurements and two-qubit operations.

(20) In summary, provided with a linear network coding solution, together with conflict-free time-codings of the directed edges and scheduling of the nodes, the method according to embodiments of the present invention generates a low-depth procedure to distribute entanglement from the transmitters to their corresponding targets, in a quantum architecture whose architecture includes a network of qubits located at nodes, where a pair of qubits located at nodes are connected in the network.

(21) The procedure according to embodiments of the method of the present invention, will now be described with reference to the drawings.

(22) FIG. 1 shows an embodiment of a quantum information processing system 101 on which embodiments of the method of the present invention may be implemented. The quantum information processing system 101 includes a compiler 102, a classical control system 103 and a quantum processor 104. The classical control system 103 is formed of a network of nodes (as will be shown in FIG. 2) and the quantum processor 104 is formed from an array of connected qubits (as will also be shown in FIG. 2).

(23) For a particular operation to be performed on the array of qubits of the quantum processor 104 (e.g. received by the compiler as a machine code set of instructions through which the operation to be performed is expressed), the compiler 102 looks up the linear network coding solution for the operation. The compiler 102 then interprets the machine code and converts the classical linear network coding solution into a set of quantum operations, which is expressed as a sequence of quantum instructions (with classical control, based on the quantum measurement outcomes) for executing by the array of qubits of the quantum processor 104 to perform the quantum operations.

(24) FIG. 2 shows a network 11 of nodes 12, with edges connecting these nodes. The nodes 12 form the nodes of a network (e.g. of the classical control system 103 shown in FIG. 1) on which a linear network coding solution is applied but also correspond to the location of qubits of a hardware platform (e.g. of the quantum processor 104 shown in FIG. 1), e.g. of a quantum information processing system. This quantum network graph that the network represents has edges for which a CNOT operation is possible in either direction.

(25) In this network 11 of nodes 12, it is desired to share a Bell pair (i.e. maximally entangle the quantum states of the qubits) between each pair of nodes 12 with the same label (a.sub.1, a.sub.2, a.sub.3, a.sub.4, a.sub.5). It can be seen that these pairs of nodes 12 are non-adjacent and are remote from each other on opposite sides of the network 11.

(26) It should be noted that the labelling of the nodes (as shown in FIGS. 3 to 21), which is inherited directly from classical binary network coding, has a direct correspondence in general to the quantum operations of the present invention that are to be performed, and not just to those of the embodiment described with reference to the Figures.

(27) FIG. 3 shows a classical linear network coding solution that achieves the desired entanglement distribution. It should be noted that this is a directed acyclic graph and every node 12 accumulates all of its inputs before forwarding outputs. It should be noted that the addition shown in FIG. 3 (and all the subsequent Figures) is always modulo 2. The linear network coding solution satisfies the requirements detailed above. FIG. 3 also shows the directed edges 14 between pairs of nodes 12.

(28) The determination of the direction of the edges of the quantum network graph thus determines which direction to use the CNOT operations for each edge, i.e. given the linear network coding solution that is taken as the input.

(29) FIG. 4 shows a scheduling derived for the network 11, shown by the shapes of the nodes. The nodes are to be taken in the order: diamond, square, circle, where a diamond represents time-slot “1” in the schedule, a square represents time-slot “2” in the schedule and a circle represents time-slot “3” in the schedule.

(30) It will be appreciated that although the scheduling that has been derived for this particular embodiment uses only three different types of nodes (corresponding to the three different shapes), the schedule for a different network may require more than three different types of nodes. When the schedule comprises four or more types of nodes, the procedure that is performed is the same as is described below for the three types of nodes, except that the part of the procedure described for the middle set of nodes (the square nodes) is repeated for each set of middle nodes (i.e. for sets 2, 3, . . . n−1, as appropriate, where there are n sets of different types of nodes).

(31) FIG. 5 shows a time-coding of the directed edges 14 between the nodes 12, labelled by the integers: 1, 2, 3 on the outbound edges. It should be observed that this time-coding is conflict free, i.e. any pair of directed edges that have the same time-code do not have either the same source node or the same target node.

(32) Provided the classical linear network coding solution as shown and described, supplemented with the time-coding and the schedule as shown and described, the procedure of the method according to embodiments of the present invention may then be implemented, as will be described.

(33) First, the state of the qubit at each node 12 is initialised in parallel. Those qubits at nodes that are not the sources of any directed edges 14 are initialised to the quantum state |0, those nodes having incoming messages from earlier scheduled nodes are also initialised to |0 and the remainder are initialised to |+. It can be seen, in FIG. 4 that taking the diamond nodes (the nodes with a time-slot “1”) first, the nodes are initialised and labelled. These include those already labelled: a.sub.1, a.sub.2, a.sub.3, a.sub.4, a.sub.5. Other diamond nodes are given new labels: L.sub.1, L.sub.2, L.sub.3, L.sub.4, L.sub.5, as shown in FIG. 5.

(34) For each node “q” that is not a receiver node and which has been given a time-slot “1” (i.e. the diamond nodes including the nodes labelled a.sub.4, L.sub.2, L.sub.3, L.sub.4 in the network 11 shown in FIG. 6), a sequence of operations involving these nodes “q” is performed: iterating through the time-codes for the directed edges 14 in order, those directed edges which have that time-code, which have this source node “q” are considered.

(35) For each such directed edge “e”, a CNOT operation is performed with control node “q” and target node “r”, where “r” is the qubit located at the node which is the target of the directed edge “e”. All of the operations for directed edges 14 associated with a given time-code may be performed simultaneously, as they involve distinct pairs of qubits.

(36) Thus, the directed edges having time-code “1” are considered first, as shown in FIG. 6. Then, the directed edges having time-code “2” are considered next, as shown in FIG. 7. Then, the directed edges having time-code “3” are considered next, as shown in FIG. 8.

(37) Next, as shown in FIGS. 9-15, operations are performed on all the qubits associated with nodes 12 that are not receiver nodes and which have been assigned time-slots “2”, “3”, . . . in order, up to A−1, where A is the limit of the number of time-slots. In the network 1 shown, A=3, so in this step operations are performed on all the qubits associated with nodes 12 that are not receiver nodes and which have been assigned the time-slot “2” (i.e. the square nodes including the node labelled a.sub.3 in the network 11 shown in FIG. 9).

(38) First, a conflict-free time-coding of the directed edges 14 between the nodes 12, labelled by the integers: 1, 2, 3 on the outbound edges, is established for the square nodes, as can be seen in FIG. 9. A similar procedure of CNOT transmission operations, as for the time-coding established for the diamond nodes, is then performed for the time-coding established for the square nodes.

(39) For this (square) time-slot “t” in the schedule and a given node “q” which is assigned the time-slot “t”, the following operations are performed: (i) Iterating through the time-codes for directed edges 14 in order, those directed edges which have that time-code and which have source node “q” are considered. For each such directed edge “e”, a CNOT operation is performed with control node “q” and target node “r”, where “r” is the qubit located at the node which is the target of the directed edge “e”. All of the operations associated with a given time-code may be performed simultaneously, as they involve distinct pairs of qubits.

(40) Thus, as shown in FIG. 9, the CNOT transmission operations are performed on the nodes 12 and directed edges 14 labelled with time-code “1”. As shown in FIG. 10, the CNOT transmission operations are performed on the nodes and directed edges labelled with time-code “2”. As shown in FIG. 11, the CNOT transmission operations are performed on the nodes and directed edges labelled with time-code “3”.

(41) Following this, the next operation in the procedure for the square nodes is performed: (ii) If there is a node “p” that is assigned an earlier time-slot than node “q” (node “q” being a square node), and which sends a message to node “q” in the linear network coding solution, the qubit at node “q” is “terminated”. To do this, a termination procedure (to implement a classical correction) and a measurement is required to be made. This termination subroutine is described in more detail below. This results in each node 12 that is not a transmitter node or a receiver node being given a new label. This is shown in FIG. 12.

(42) Following this: (iii) If there is a node “u” which is assigned a later time-slot than node “q” (node “q” being a square node), and which sends a message to node “q” in the linear network coding solution, an additional CNOT operation is performed with control node “q” and targets “r”, for those nodes “r” which are the targets of directed edges “e” whose source is node “p”. These CNOT operations are performed in the same order as in step (i) above. This step of the procedure prepares such nodes “u” that are involved later in the process (i.e. at a subsequent timeslot), so that these node will be correctly setup for operations performed later on.

(43) Thus, as shown in FIG. 13, the CNOT transmission operations are performed on the nodes 12 and directed edges 14 labelled with time-code “1”, using the newly labelled nodes 12 from the termination subroutine. As shown in FIG. 14, the CNOT transmission operations are performed on the nodes and directed edges labelled with time-code “2”. As shown in FIG. 15, the CNOT transmission operations are performed on the nodes and directed edges labelled with time-code “3”.

(44) After the operations for these intermediate time-slots, as will be shown in FIGS. 16-18, operations are performed on all the qubits associated with nodes 12 that are not receiver nodes and which have been assigned the last time-slots. In the network 1 shown, A=3, so in this step operations are performed on all the qubits associated with nodes 12 that are not receiver nodes and which have been assigned the time-slot “3” (i.e. the circle nodes including the nodes labelled a.sub.1 and as in the network 11 shown in FIG. 16).

(45) First, a conflict-free time-coding of the directed edges 14 between the nodes 12, labelled by the integers: 1, 2, 3 on the outbound edges, is established for the circle nodes, as can be seen in FIG. 16. A similar procedure of CNOT transmission operations, as for the time-coding established for the diamond and square nodes, is then performed for the time-coding established for the circle nodes.

(46) As shown in FIG. 16, for this (circle) time slot “t” in the schedule and a given node “q” that is assigned the time-slot “t”, and which is also not a receiver node in the linear network coding solution, the following sequence of operations is performed: iterating through the time-codes for directed edges 14 in order, those directed edges which have that time-code and which have source node “q” are considered. For each such directed edge “e”, a CNOT operation is performed with control node “q” and target node “r”, where “r” is the qubit located at the node which is the target of the directed edge “e”. All of the operations associated with a given time-code may be performed simultaneously, as they involve distinct pairs of qubits.

(47) Thus, as shown in FIG. 16, the CNOT transmission operations are performed on the nodes 12 and directed edges 14 labelled with time-code “1”. As shown in FIG. 17, the CNOT transmission operations are performed on the nodes and directed edges labelled with time-code “2”. As shown in FIG. 18, the CNOT transmission operations are performed on the nodes and directed edges labelled with time-code “3”.

(48) After these operations have been performed, a termination procedure (to implement a classical correction) is performed and a measurement is made, based on the values shown in FIG. 19 (the same as FIG. 18 but not showing the time-coding). All relay node qubits “q” (i.e. those which are not transmitter or receiver nodes) and which are assigned to a time-slot “A” (i.e. of the circle nodes) are terminated. The circle nodes are measured in the X basis. The termination subroutine is described below.

(49) Concurrently, for all other relay qubits “r”, the (red and square) qubits “r” are measured in the standard (Z) basis, recording the measurement outcome as y.sub.r.

(50) In parallel, for each qubit “q” at a receiver node, an X operation is performed, if w.sub.q=1 and if qubit “q” is also not subject to a Z operation as a result of a termination for some other qubit. (If w.sub.q=1 and qubit “q” is also subject to such a Z operation, a single Z.sup.v X.sup.w operation may be performed instead of performing them separately.) This allows this step to be performed concurrently with the termination and measurement step.

(51) The above procedure is a “delayed signal correction”, where w.sub.q is defined for each node “q”, as follows: For each relay node “q”, a hypothetical “measurement result” variable y.sub.q is defined, which may take values 0 or 1. For transmitter nodes “q”, the hypothetical “measurement result” variable is set to y.sub.q=0. For each node “q”, w.sub.q is defined to be the sum modulo 2 of (y.sub.r+w.sub.r is defined), for r ranging over all neighbours of q which are the sources of directed edges whose targets are q. If there are no such neighbours of r, the delayed signal correction is defined to be w.sub.q=0.

(52) FIG. 20 shows the outputs, symbolised as outputs “B”, for the measurement outcomes. This gives the following equations:
B.sub.2=a.sub.1+a.sub.2+a.sub.3+a.sub.4+L.sub.6
B.sub.3=a.sub.2+a.sub.3+a.sub.4+a.sub.5+L.sub.7
B.sub.4=a.sub.1+a.sub.2+L.sub.1+L.sub.6
B.sub.5=a.sub.3+L.sub.2+L.sub.6+L.sub.7
B.sub.6=a.sub.4+a.sub.5+L.sub.3+L.sub.7
B.sub.9=a.sub.2+L.sub.4+L.sub.6+L.sub.8+L.sub.9
B.sub.10=a.sub.2+L.sub.1+L.sub.2+L.sub.6+L.sub.8
B.sub.11=a.sub.4+L.sub.2+L.sub.3+L.sub.7+L.sub.10
B.sub.12=a.sub.2+a.sub.4+L.sub.1+L.sub.3+L.sub.6+L.sub.7+L.sub.9
B.sub.13=a.sub.4+L.sub.5+L.sub.7+L.sub.9+L.sub.10

(53) These equations can be rearranged to give:
L.sub.1=a.sub.3+a.sub.4+B.sub.2+B.sub.4
L.sub.2=a.sub.1+a.sub.3+a.sub.5+B.sub.2+B.sub.3+B.sub.5
L.sub.3=a.sub.2+a.sub.3+B.sub.3+B.sub.6
L.sub.4=a.sub.4+B.sub.3+B.sub.5+B.sub.6+B.sub.9+B.sub.10+B.sub.12
L.sub.5=a.sub.2+B.sub.2+B.sub.4+B.sub.5+B.sub.10+B.sub.11+B.sub.13
L.sub.6=a.sub.1+a.sub.2+a.sub.3+a.sub.4+B.sub.2
L.sub.7=a.sub.2+a.sub.3+a.sub.4+a.sub.5+B.sub.3
L.sub.8=a.sub.3+a.sub.5+B.sub.2+B.sub.3+B.sub.4+B.sub.5+B.sub.9

(54) These can be used to represent the labels at the receiver nodes. From this, it can be seen that each receiver node has the right node formula plus some “B” terms. These are the classical measurement outcomes, as shown in FIG. 21. If the “B” terms sum to one (1) in any receiver node, then a Pauli-X gate is performed on the qubit at this receiver node.

(55) From the above, it can be seen that the procedure takes 17 steps (layers of operations), that are formed from 3 single qubit gates, 2 measurements and 12 two-qubit gates. It will be noted that every pair of paths cross; therefore, were only edge-disjoint entanglement distribution to be performed, the following steps would need to be performed 5 times in series: prepare some |+ states, odds then evens two-qubit gates, measure, classical correct. In total, this would result in 20 layers of operations: 10 two-qubit gates, 5 measurements and 10 single qubit gates.

(56) Using the method according to this embodiment of the present invention therefore provides a reduction from 25 to 17 layers of operations. More significantly, however, the method according to this embodiment of the present invention results in 14 layers of measurements and two qubit gates (which are more difficult operations to perform), compared with 15 layers with the edge-disjoint approach. It will be appreciated that the bigger the network, the bigger the gain.

(57) The embodiment of the present invention, as outlined above, makes use of a subroutine denoted as “termination of a qubit”. The effect of “terminating” a qubit is (i) to realise or simulate a measurement of the qubit in the |+, |− basis, and (ii) in the case that the outcome is |−, performing suitable Z corrections on some others of the qubits to bring about the post-measurement state of those qubits that would have been realised if the outcome of the measurement had instead been |+.

(58) It is possible to show that this notion of “termination” may be realised under certain circumstances, and in particular under every circumstance in which it may be used with the embodiment described above.

(59) In many cases, there may not be a unique way in which to terminate a qubit, and in general the ways in which a qubit may be terminated depend meaningfully on the operations that have been performed on that qubit and the others in the procedure. Thus, the problem of determining how to terminate a qubit may be non-trivial. Below, one procedure to solve this problem is described, according to an embodiment of the present invention, which enables the decisions enumerated as part of the termination subroutine to be made easily. The techniques described incorporate the termination of qubits as part of the complete process, and extend to all ways in which this effect may be used as part of the procedure described below, howsoever those processes are performed or determined. It will be appreciated that any method of keeping track of the quantum state as part of the termination subroutine may be used.

(60) In the case of termination, a (classical) state-vector simulation of the entanglement distribution procedure that is being run on the quantum computer is performed. This enables the state of the quantum circuit to be tracked, so it can be determined which corrections are needed in the termination subroutine (and then performing the corrections determined to be needed). It may be possible to perform this concurrent simulation efficiently classically.

(61) The purpose of termination of a qubit is as follows. Let the first qubit be that which is to be terminated; in general the quantum state prior to termination can be described as one of two possibilities (the below are not normalised):
|0|ψ+|1|ψ
or
|x|ψ′

(62) Where |x is any of |0, |1, |+, |− and |ψ, |ψ, |ψ′ are general quantum states corresponding to the remaining qubits (those that are not to be terminated).

(63) In the former case, the goal of termination is to perform operations to obtain the state (not normalised):
|+(|ψ+|ψ)

(64) This involves: first measurement of the first qubit in the X-basis, then classical operations on some of the other qubits if the outcome is |−.

(65) In the latter case, the goal of termination is to perform operations to obtain the state (not normalised):
|+|ψ′

(66) This involves identifying the state of the first qubit (i.e. which of |0, |1, |+, |− that |x is), either directly from the classical state-vector simulation or by performing a X-basis measurement, then performing a single-qubit quantum operation to put the qubit in the state |+ if necessary.

(67) As part of the technique to compile a set of operations in accordance with embodiments of the present invention, a representation of the state of the n qubits involved in the entanglement distribution procedure is used, which suffices to describe (simulate classically) the effect of those operations which are involved in that procedure, to determine the corrections that are to be made to the other qubits of the array (i.e. those that are not being terminated). This representation, which is denoted as a “parity function tableau”, comprises an array C with at most n+1 rows and n+1 columns, supplemented by a further column p with at most n+1 rows. The entries of C and p comprise noughts (0s) and ones (1s). These entries, and the number of rows in C and in p, may change in the course of compiling the operations to perform the entanglement distribution procedure in order to track the changes to the state of the system which would occur as that procedure is executed.

(68) The means by which the changing state of the qubits involved in the entanglement distribution procedure is represented is as follows. Consider a procedure that involves a number of qubits, indexed by integers 1, 2, . . . , n, and which are all initialised either to the state |0 or the state |+. A list q.sub.1, q.sub.2, . . . , q.sub.k of the indices is defined, in increasing order, corresponding to qubits initialised in the state |+.

(69) To represent the initial state, an array C and a column p is used, each of which has a number of rows which is one more than the number of qubits k initialised to the state |+. The number of columns of C is n+1. The columns of C are indexed by integers 0, 1, 2, . . . , n, and the rows of both C and p by integers 0, 1, 2, . . . , k.

(70) Column 0 of C has entries comprising a 1 in row 0, and 0 in all other rows. For each row j ranging from 1 up to k, column q.sub.j has an entry of 1 in row j, and 0 in all other rows. The column p and all other columns of C have entries which are all 0.

(71) The effect of each operation in the procedure—comprising Pauli X and Z operations, CNOT operations, and measurements in the |0, |1 basis or the |+, |− basis—is simulated as follows: For an X operation on some qubit with index j: toggle the value of the entry in column j, row 0 of the array C between 0 and 1. For a Z operation on some qubit with index j: for each row r in which the entry in column j of C is equal to 1, toggle the value of the entry in row r of p between 0 and 1. For a CNOT operation whose control is a qubit with index h, and whose target is a qubit with index/for each row r in which the entry in column h of C is equal to 1, toggle the entry in row r of column h of C between 0 and 1. For a measurement in either the |0, |1 basis or the |+, |− basis on a qubit with index j, first compute an equivalent representation of the pre-measurement state, transforming the array C and the column p, as follows: 1) Define an array D, comprising C with an extra column comprising the entries of p. 2) Put D into a “row echelon form”, in which column j is either a pivot column, zero, or equal to column 0. 3) Having put D in row echelon form, take the final column of D as a revised value of p, and the remaining columns as a revised value of C. For a measurement in the |0, |1 basis on some qubit with index j, the operations performed depends on the entries in column j of the array C. The transformation based on a row echelon form ensures that column j of C is either entirely 0, equal to column 0 of C, or has a single entry 1 in some row r>1. If column j of C is entirely 0 or equal to column 0 of C, there is no change to C or to the column p. The measurement outcome is taken to be the entry in row 0 of column j of C; the measurement outcome is deterministic in this case. If column j of C has a single 1 in row r>1, select a measurement outcome y to represent the measurement outcome. (The value of y may be fixed to consider the effect of a particular outcome, or chosen uniformly at random to simulate the distribution of outcomes which would be observed in practice under ideal conditions.) If y is equal to 1, toggle the entry in row 0 of any column h in which the entry in row r is equal to 1, and also toggle the entry in row 0 of p if the entry in row r is equal to 1. Having done this, then remove the row r entirely from C and from p, re-indexing all rows numbered higher than r. For a measurement in the |+, |− basis on some qubit with index j, the operations performed depend on the entries in column j of the array C. The transformation based on a row echelon form ensures that column j of C is either entirely 0, equal to column 0 of C, or has a single entry 1 in some row r>1. If column j of C has a single 1 in some row r>1, and row r has only the single 1 entry in column j, there is no change to C or to the column p. The measurement outcome is taken to be |+ if the entry in row r of p is equal to 0, and |−otherwise; the measurement outcome is deterministic in this case. If column j of C has a single 1 in some row r>1, but row r has more than one entry which is 1; or if column j of C has no 1 entries in any row r>1; then add a new row to the bottom of C and of p with index k+1, with entries all 0, and proceed as follows. Select a measurement outcome y to represent the measurement outcome, where y=0 denotes a |+ outcome and y=1 denotes a |− outcome. (The value of y may be fixed to consider the effect of a particular outcome, or chosen uniformly at random to simulate the distribution of outcomes which would be observed in practice under ideal conditions.) Then toggle the entry in row k+1 of column j, and also in row k+1 of p in the case that y=1. If column j has any other entries of 1 in a row 0<r<k+1, we also toggle the entry in row r of column j, and also in row r of p in the case that y=1.

(72) Note that, in the above procedure, there is a simple distinction between the ways in which the array C and the column p are modified, depending on the bit y representing the outcome of a |+, |− basis measurement. Specifically, in the case of a |+, |− basis measurement whose outcome y is not deterministic, the difference is in one or two entries of p which may be toggled if y=1, corresponding to a measurement outcome of |−. Specifically, the entries which may be toggled are in the newly introduced row k+1, and in the case that column j has an entry of 1 in some row r>0 which has more than one entry of 1, also in the row r.

(73) Let p.sub.0 and p.sub.1 be columns of length k+2, representing the two possible values of p depending on whether y=0 or y=1. Consider the difference between p.sub.0 and p.sub.1, represented by a column d of length k+2 which has a 1 in every row where p.sub.0 and p.sub.1 differ and a 0 in every row where they agree. Consider a “system of linear equations” C*x=d, representing in a well-defined mathematical way how the column d may be described in terms of a sum modulo 2 of columns of the array C.

(74) It is possible to show that a solution x always exists, comprising a column of length n+1, indexed from 0 up to n. If Q is the set of integers corresponding to rows in which x has an entry of 1, it is possible (from the construction of the system of equations C*x=c) that simulating a Z operation on each qubit q in Q suffices to transform the post-measurement state corresponding to the outcome |−, to the post-measurement state corresponding to the outcome |+, which is witnessed by the fact that simulating this operation using the array C and the column p.sub.1 yields the same array C and the column p.sub.0. Thus, we may realise the effect of “terminating the qubit j” by performing a |+, |− basis measurement on j, and (conditioned on obtaining the outcome |−) performing Z operations on a set of qubits Q determined in this manner.

(75) Having defined the effect of “qubit termination” in this way, and having described one way to realise this effect in the setting in which the techniques are defined by means of pre-computed operations, this subroutine may be used with the embodiments outlined above.

(76) In terms of the labels used to denote particular quantum states of the qubits, as shown in the Figures, if the labelled formula of some node is independent of all other node formulae, or it is linearly dependent on formulae of nodes that have already been measured in the Z-basis, then the qubit at that node can be measured safely in the Z-basis. Alternatively, if the formula of the node to be measured is neither of these, then the X-basis is used for the measurement. If the outcome |− is measured, the termination subroutine applies Z gates to a subset of the other nodes, chosen such that the sums of the node formulae of the chosen nodes sum to the node formula of the terminated qubit. Such a subset can always be chosen because this condition has already been defined to apply only when the formula of the node to be terminated is not linearly independent of the other node formulae.

(77) It will be seen from the above that, in at least preferred embodiments, the present invention provides a method of operating a quantum information processing system, and a quantum information processing system, that operates more efficiently and quickly, owing to the fewer steps in the sequence that results from not having the problem of sequentiality. It thus reduces the depth of the network, in a way that independent of the size of the network or the distance over which entanglement is to be distributed. This helps both to reduce the susceptibility of the quantum information processing system to loss of coherence between the qubits and noise in the system, which allows a practical realisation of operations on quantum architectures, and to reduce the time taken to perform the necessary operations.