Efficient synthesis of optimal multi-qubit Clifford circuits
Systems and techniques that facilitate efficient synthesis of optimal multi-qubit Clifford circuits are provided. In various embodiments, a system can receive as input a number n representing a quantity of qubits. In various instances, the system can generate, via a cost-invariant reduction function, as output a library of different n-qubit canonical representatives that respectively correspond to different cost-invariant equivalence classes of n-qubit Clifford group elements. In various embodiments, a system can receive as input a first Clifford group element. In various aspects, the system can search a database of canonical representatives, wherein different canonical representatives in the database respectively correspond to different cost-invariant equivalence classes of Clifford group elements. In various cases, the system can identify based on the search a second Clifford group element that implements the first Clifford group element and that has a lower entangling-gate cost than the first Clifford group element.
1. A system, comprising:
a processor that executes computer-executable components stored in a memory, the computer-executable components comprising:
a library component that, for a number n representing a quantity of qubits, generates, via a cost-invariant reduction function, a library of different n-qubit canonical representatives that respectively correspond to different cost-invariant equivalence classes of n-qubit Clifford group elements,
wherein the cost-invariant equivalence classes are classes that are equivalent in terms of entangling-gate cost, and wherein n≤6;
a compiling component that:
receives as input a suboptimal n-qubit Clifford operator;
computes the cost of the suboptimal n-qubit Clifford operator; and
search the library of n-qubit canonical representatives and determine or identify an optimal n-qubit Clifford operator that implements the suboptimal n-qubit Clifford operator and is lower cost than the cost of the suboptimal n-qubit Clifford operator.
2. The system of claim 1 , wherein a first n-qubit canonical representative in the library of different n-qubit canonical representatives respectively corresponds to a first equivalence class of the different cost-invariant equivalence classes, and wherein the first n-qubit canonical representative is a lexicographically minimum element in the first equivalence class.
3. The system of claim 2 , wherein the library component computes the first n-qubit canonical representative via the cost-invariant reduction function and based on an n-qubit Clifford group element U in the first equivalence class, wherein the cost-invariant reduction function is given by:
Reduce
(
U
)
=
arg
min
W
∈
S
n
min
L
,
R
∈
L
o
c
L
W
U
W
-
1
R
where Reduce (U) represents the first n-qubit canonical representative, where S n represents a set of n-qubit permutations, where W represents an n-qubit permutation from S n , where Loc represents a local subset of Clifford group elements, and where L and R represent local Clifford group elements from Loc.
4. The system of claim 3 , further comprising:
a pruning component that prunes S n and Loc according to a subgroup-adapted order that prioritizes qubit permutations over local Clifford group elements and that prioritizes left multiplications by local Clifford group elements over right multiplications by local Clifford group elements.
5. The system of claim 2 , wherein the first n-qubit canonical representative is specified up to a phase by a set of bit strings that indicate how the first n-qubit canonical representative maps various Pauli operators to other Pauli operators, and wherein the first n-qubit canonical representative is stored in the library according to a thin matrix binary format which omits a portion of the set of bit strings.
6. A computer-implemented method, comprising:
receiving, by a device operatively coupled to a processor, as input a number n representing a quantity of qubits; and
generating, by the device and via a cost-invariant reduction function, as output a library of different n-qubit canonical representatives that respectively correspond to different cost-invariant equivalence classes of n-qubit Clifford group elements, wherein the cost-invariant equivalence classes are classes that are equivalent in terms of entangling-gate cost;
receiving, by the device, as input a suboptimal n-qubit Clifford operator;
computing, by the device, the cost of the suboptimal n-qubit Clifford operator; and
searching, by the device, the library of n-qubit canonical representatives and determining or identifying an optimal n-qubit Clifford operator that implements the suboptimal n-qubit Clifford operator and is lower cost than the cost of the suboptimal n-qubit Clifford operator.
7. The computer-implemented method of claim 6 , wherein a first n-qubit canonical representative in the library of different n-qubit canonical representatives respectively corresponds to a first equivalence class of the different cost-invariant equivalence classes, and wherein the first n-qubit canonical representative is a lexicographically minimum element in the first equivalence class.
8. The computer-implemented method of claim 7 , further comprising:
computing, by the device, the first n-qubit canonical representative via the cost-invariant reduction function and based on an n-qubit Clifford group element U in the first equivalence class, wherein the cost-invariant reduction function is given by:
Reduce
(
U
)
=
arg
min
W
∈
S
n
min
L
,
R
∈
L
o
c
L
W
U
W
-
1
R
where Reduce (U) represents the first n-qubit canonical representative, where S n represents a set of n-qubit permutations, where W represents an n-qubit permutation from S n , where Loc represents a local subset of Clifford group elements, and where L and R represent local Clifford group elements from Loc.
9. The computer-implemented method of claim 8 , further comprising:
pruning, by the device, S n and Loc according to a subgroup-adapted order that prioritizes qubit permutations over local Clifford group elements and that prioritizes left multiplications by local Clifford group elements over right multiplications by local Clifford group elements.
10. The computer-implemented method of claim 7 , wherein the first n-qubit canonical representative is specified up to a phase by a set of bit strings that indicate how the first n-qubit canonical representative maps various Pauli operators to other Pauli operators, and wherein the first n-qubit canonical representative is stored in the library according to a thin matrix binary format which omits a portion of the set of bit strings.
11. A computer program product for facilitating synthesis of Clifford circuits, the computer program product comprising a computer readable memory having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
receive as input a number n representing a quantity of qubits; and
apply a cost-invariant reduction function and generate, as a result of the application, a library of different n-qubit canonical representatives that respectively correspond to different cost-invariant equivalence classes of n-qubit Clifford group elements, wherein the cost-invariant equivalence classes are classes that are equivalent in terms of entangling-gate cost;
receive as input a suboptimal n-qubit Clifford operator;
compute the cost of the suboptimal n-qubit Clifford operator; and
search the library of n-qubit canonical representatives and determining or identifying an optimal n-qubit Clifford operator that implements the suboptimal n-qubit Clifford operator and is lower cost than the cost of the suboptimal n-qubit Clifford operator.
12. The computer program product of claim 11 , wherein a first n-qubit canonical representative in the library of different n-qubit canonical representatives respectively corresponds to a first equivalence class of the different cost-invariant equivalence classes, and wherein the first n-qubit canonical representative is a lexicographically minimum element in the first equivalence class.
13. The computer program product of claim 12 , wherein the program instructions are further executable to cause the processor to:
compute the first n-qubit canonical representative via the cost-invariant reduction function and based on an n-qubit Clifford group element U in the first equivalence class, wherein the cost-invariant reduction function is given by:
Reduce
(
U
)
=
arg
min
W
∈
S
n
min
L
,
R
∈
L
o
c
L
W
U
W
-
1
R
where Reduce (U) represents the first n-qubit canonical representative, where S n represents a set of n-qubit permutations, where W represents an n-qubit permutation from S n , where Loc represents a local subset of Clifford group elements, and where L and R represent local Clifford group elements from Loc.
14. The computer program product of claim 13 , wherein the program instructions are further executable to cause the processor to:
prune S n and Loc according to a subgroup-adapted order that prioritizes qubit permutations over local Clifford group elements and that prioritizes left multiplications by local Clifford group elements over right multiplications by local Clifford group elements.
15. The computer program product of claim 12 , wherein the first n-qubit canonical representative is specified up to a phase by a set of bit strings that indicate how the first n-qubit canonical representative maps various Pauli operators to other Pauli operators, and wherein the first n-qubit canonical representative is stored in the library according to a thin matrix binary format which omits a portion of the set of bit strings.