Efficient synthesis of optimal multi-qubit Clifford circuits

Patent metadata

Field	Value
Publication number	US-12288127-B2
Application number	US-202017066916-A
Country	US
Kind code	B2
Filing date	Oct 9, 2020
Priority date	Oct 9, 2020
Publication date	Apr 29, 2025
Grant date	Apr 29, 2025

Abstract

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.

First claim

What is claimed is:

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

⁢

Assignees

• IBM

Inventors

• Bravyi Sergey
• Latone Joseph
• Maslov Dmitri

Classifications

• G06F7/76

  Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06N10/00 Primary

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title

• G06N10/20 Primary

  Models of quantum computing, e.g. quantum circuits or universal quantum computers · CPC title