Quantum circuit simulation
An apparatus and method for simulating a quantum circuit are provided. In particular, an indication of a subset of input and output qubits of the quantum circuit is received. The indicated subset corresponds to an amplitude tensor of the quantum circuit that is to be determined, wherein the amplitude tensor comprises amplitudes for different combinations of states of the qubits of the indicated subset. Using a tensor network of the quantum circuit and Restricted Maximum Cardinality Search (RMCS), an elimination order of intermediate qubits within the quantum circuit is determined. The amplitude tensor is determined by removing, successively in accordance with the elimination order, that indices of the tensors of the tensor network that correspond to the intermediate qubits from the tensor network.
1 . An apparatus for simulating a quantum circuit for at least one of verification and validation of a quantum processor, the apparatus including a processing circuitry configured to:
receive an indication of a subset of input and output qubits of the quantum circuit, the indicated subset corresponding to an amplitude tensor of the quantum circuit that is to be determined, the amplitude tensor comprising amplitudes for different combinations of states of qubits of the indicated subset;
determine, using a tensor network of the quantum circuit and Maximum Cardinality Search (MCS), an elimination order of intermediate qubits within the quantum circuit,
wherein the qubits of the indicated subset are placed at an end of an elimination sequence of the elimination order; and
determine the amplitude tensor by removing, successively in accordance with the elimination order, indices of tensors of the tensor network that correspond to the intermediate qubits from the tensor network;
wherein qubits, unique indices among the indices of tensors, and vertices are in a one-to-one-to-one correspondence.
2 . The apparatus according to claim 1 , wherein the elimination order is determined iteratively, in a reverse order, by selecting from the intermediate qubits, in each process of the iteration, an intermediate qubit that has not been selected in any preceding process of the iteration, and corresponds to, in a chordal graph representing the tensor network, a vertex neighboring a maximum number of vertices that correspond to either the following (a) or (b):
(a) an intermediate qubit that has been selected in any preceding process of the iteration, or
(b) a qubit in the indicated subset.
3 . The apparatus according to claim 2 , wherein each intermediate qubit uniquely corresponds to a respective index of the tensors, each qubit in the indicated subset uniquely corresponds to a respective index of the tensors, and each index of the tensors uniquely corresponds to either an input qubit, an output qubit, or an intermediate qubit; and/or
a one-to-one correspondence exists between the vertices of the chordal graph and indices that correspond to either an intermediate qubit or a qubit in the indicated subset.
4 . The apparatus according to claim 2 , wherein the chordal graph representing the tensor network is a chordal completion of a non-chordal graph representing the tensor network that has a minimized maximal clique among chordal completions of the non-chordal graph.
5 . The apparatus according to claim 4 , wherein the chordal graph is obtained from the non-chordal graph representing the tensor network using an optimized elimination order of the vertices of the non-chordal graph,
wherein the chordal graph is obtained by adding edges to the non-chordal graph such that, for each vertex, all neighbors of the vertex that are later in the optimized elimination order than the vertex are a clique in the chordal graph.
6 . The apparatus according to claim 5 , wherein for each quantum gate of the quantum circuit, there is a tensor of the tensor network that has, for each qubit of the quantum gate that is either an intermediate qubit or in the indicated subset, one index that corresponds to the qubit;
for each quantum gate of the quantum circuit, that vertices of the non-chordal graph that correspond to the qubits of the quantum gate are a clique.
7 . The apparatus according to claim 6 , wherein the determining of the elimination order of the intermediate qubits includes: determining the optimized elimination order.
8 . The apparatus according to claim 7 , wherein the optimized elimination order of the vertices of the non-chordal graph representing the tensor network is determined using an optimization procedure,
wherein the optimization procedure minimizes a maximal clique of a graph that is obtained by adding edges to the non-chordal graph such that, for each vertex of the graph, all neighbors of the vertex that are later in the optimized elimination order than the vertex are a clique in the graph.
9 . The apparatus according to claim 7 , wherein before determining of the optimized elimination order, the non-chordal graph is modified by adding, to the non-chordal graph, edges such that the vertices corresponding to the qubits of the indicated subset are a clique.
10 . The apparatus according to claim 1 , wherein the processing circuitry is configured to:
determine, in accordance with the indicated subset, a non-chordal graph representing the tensor network such that both of the following situations (i) and (ii) exist:
(i) a one-to-one correspondence exists between the vertices of the non-chordal graph and indices of the tensors that correspond to either an intermediate qubit or a qubit in the indicated subset; and
(ii) for each tensor of the tensor network, the vertices of the non-chordal graph that correspond to the tensor are a clique.
11 . The apparatus according to claim 1 , wherein the processing circuitry is configured to:
determine, in accordance with the indicated subset, a non-chordal graph representing the tensor network from a generic non-chordal graph representing the tensor network by adding the following (a) and (b):
(a) for each input or output qubit that is in the indicated subset, a single vertex that corresponds to said qubit, and
(b) edges, such that, for each quantum gate of the quantum circuit, vertices of the non-chordal graph that correspond to the qubits of the quantum gate are a clique,
wherein there is a one-to-one correspondence between the vertices of the generic non-chordal graph and the intermediate qubits.
12 . The apparatus according to claim 1 wherein the processing circuitry is configured to:
determine, in accordance with the indicated subset, a non-chordal graph representing the tensor network from a universal non-chordal graph representing the tensor network by removing, for each input or output qubit that is not in the indicated subset, both of the following (a) and (b):
(a) all edges connecting a vertex that corresponds to the qubit, and
(b) all vertices that correspond to the qubit;
wherein there is a one-to-one correspondence between the vertices of the universal non-chordal graph and qubits of the quantum circuit, wherein each qubit of the quantum circuit is either an input qubit, an output qubit, or an intermediate qubit.
13 . The apparatus according to claim 1 , wherein the processing circuitry is configured to:
remove, before removing the indices corresponding to the intermediate qubits, indices from the tensors of the tensor network that correspond to either an input qubit that is not in the indicated subset, or an output qubit that is not in the indicated subset.
14 . The apparatus according to claim 1 , wherein the indices corresponding to either an input qubit that is not in the indicated subset or an output qubit that is not in the indicated subset are removed from the tensor network by setting the indices to respective predetermined values; and/or
the indices corresponding to the intermediate qubits are removed from the tensor network by contraction.
15 . A method for simulating a quantum circuit for at least one of verification and validation of a quantum processor, applied to a processing circuitry of an apparatus, the method comprising:
receiving an indication of a subset of input and output qubits of the quantum circuit, the indicated subset corresponding to an amplitude tensor of the quantum circuit that is to be determined, the amplitude tensor comprising amplitudes for different combinations of states of qubits of the indicated subset;
determining, using a tensor network of the quantum circuit and Maximum Cardinality Search (MCS), an elimination order of intermediate qubits within the quantum circuit,
wherein the qubits of the indicated subset are placed at an end of an elimination sequence of the elimination order; and
determining the amplitude tensor by removing, successively in accordance with the elimination order, indices of the tensors of the tensor network that correspond to the intermediate qubits from the tensor network,
wherein qubits, unique indices among the indices of tensors, and vertices are in a one-to-one-to-one correspondence.
16 . The method according to claim 15 , wherein the elimination order is determined iteratively, in a reverse order, by selecting from the intermediate qubits, in each process of the iteration, an intermediate qubit that has not been selected in any preceding process of the iteration, and corresponds to, in a chordal graph representing the tensor network, a vertex neighboring a maximum number of vertices that correspond to either the following (a) or (b):
(a) an intermediate qubit that has been selected in any preceding process of the iteration, or
(b) a qubit in the indicated subset.
17 . The method according to claim 16 , wherein each intermediate qubit uniquely corresponds to a respective index of the tensors, each qubit in the indicated subset uniquely corresponds to a respective index of the tensors, and each index of the tensors uniquely corresponds to either an input qubit, an output qubit, or an intermediate qubit; and/or
a one-to-one correspondence exists between the vertices of the chordal graph and indices that correspond to either an intermediate qubit or a qubit in the indicated subset.
18 . A non-transitory computer-readable medium, comprising processor-executable instructions which, when executed by a processing circuitry of an apparatus, cause the apparatus to implement a method for simulating a quantum circuit for at least one of verification and validation of a quantum processor, the method comprising:
receiving an indication of a subset of input and output qubits of the quantum circuit, the indicated subset corresponding to an amplitude tensor of the quantum circuit that is to be determined, the amplitude tensor comprising amplitudes for different combinations of states of qubits of the indicated subset;
determining, using a tensor network of the quantum circuit and Maximum Cardinality Search (MCS), an elimination order of intermediate qubits within the quantum circuit,
wherein the qubits of the indicated subset are placed at an end of an elimination sequence of the elimination order; and
determining the amplitude tensor by removing, successively in accordance with the elimination order, indices of the tensors of the tensor network that correspond to the intermediate qubits from the tensor network,
wherein qubits, unique indices among the indices of tensors, and vertices are in a one-to-one-to-one correspondence.
19 . The non-transitory computer-readable medium according to claim 18 , wherein the elimination order is determined iteratively, in a reverse order, by selecting from the intermediate qubits, in each process of the iteration, an intermediate qubit that has not been selected in any preceding process of the iteration, and corresponds to, in a chordal graph representing the tensor network, a vertex neighboring a maximum number of vertices that correspond to either the following (a) or (b):
(a) an intermediate qubit that has been selected in any preceding process of the iteration, or
(b) a qubit in the indicated subset.
20 . The non-transitory computer-readable medium according to claim 19 , wherein each intermediate qubit uniquely corresponds to a respective index of the tensors, each qubit in the indicated subset uniquely corresponds to a respective index of the tensors, and each index of the tensors uniquely corresponds to either an input qubit, an output qubit, or an intermediate qubit; and/or
a one-to-one correspondence exists between the vertices of the chordal graph and indices that correspond to either an intermediate qubit or a qubit in the indicated subset.