Partitioned template matching and symbolic peephole optimization

Patent metadata

Field	Value
Publication number	US-11983605-B2
Application number	US-202017082844-A
Country	US
Kind code	B2
Filing date	Oct 28, 2020
Priority date	Oct 28, 2020
Publication date	May 14, 2024
Grant date	May 14, 2024

Abstract

Systems and techniques that facilitate partitioned template matching and/or symbolic peephole optimization are provided. In various embodiments, a system can comprise a template component, which can perform template matching on a Clifford circuit associated with a set of qubits. In various aspects, the system can comprise a partition component, which can partition, prior to the template matching, the Clifford circuit into a computation stage, a Pauli stage, and a SWAP stage. In various instances, the template matching can be performed on the computation stage. In various embodiments, the system can comprise a symbolic component, which can select a subset of qubits from the set of qubits, rewrite at least one entangling gate in the computation stage such that a target of the at least one entangling gate is in the subset of qubits, and replace the at least one rewired entangling gate with a symbolic Pauli gate. In various cases, the symbolic Pauli gate can be a Pauli gate that is controlled by a symbolic variable. In various aspects, the system can comprise a peephole component, which can perform peephole optimization on the subset of qubits with the symbolic Pauli gate by implementing a dynamic programming algorithm.

First claim

What is claimed is:

1. A system, comprising:
a processor that executes computer-executable components stored in a computer-readable memory, the computer-executable components comprising:
a template component that performs, using a library of templates comprising gates, template matching on a Clifford circuit associated with a set of qubits; and
a partition component that partitions, prior to the template matching, the Clifford circuit into a computation stage, a Pauli stage, and a SWAP stage, wherein the template matching is performed on the computation stage, and wherein:
the computation state comprises all Hadamard gates, all Phase gates, and all Controlled NOT gates of the Clifford circuit, and does not comprise any Pauli gates and any SWAP gates of the Clifford circuit;
the Pauli stage comprises all Pauli gates of the Clifford circuit, and does not comprise any Hadamard gates, any Phase gates, any Controlled NOT gates, and any SWAP gates of the Clifford circuit; and
the SWAP stage comprises all SWAP gates of the Clifford circuit, and does not comprise any Hadamard gates, any Phase gates, any Controlled NOT gates, and any Pauli gates of the Clifford circuit.

2. The system of claim 1 , further comprising:
a floating component that pushes a blocking gate out of a template matching range in the computation stage by replacing the blocking gate with a linear combination of Pauli gates.

3. The system of claim 1 , wherein the partition component re-partitions the Clifford circuit when performance of the template matching in the computation stage yields a Pauli gate or a SWAP gate in the computation stage.

4. The system of claim 1 , further comprising:
a symbolic component that selects a subset of qubits from the set of qubits, rewires at least one entangling gate in the computation stage such that a target of the at least one entangling gate is in the subset of qubits, and replaces the at least one rewired entangling gate with a symbolic Pauli gate, wherein the symbolic Pauli gate is a Pauli gate that is controlled by a symbolic variable.

5. The system of claim 4 , further comprising:
a peephole component that performs peephole optimization on the subset of qubits with the symbolic Pauli gate by implementing a dynamic programming algorithm.

6. The system of claim 1 , wherein the template component, in response to determining that the Clifford circuit is optimized with respect to two-qubit gate count, restrict the template matching to a subset of the templates that can reduce single-qubit gate count without also reducing the two-bit gate count.

7. The system of claim 6 , wherein the subset of the templates comprises single-qubit templates.

8. The system of claim 6 , wherein the subset of the templates comprises templates with an even number of two-bit gates.

9. A computer-implemented method, comprising:
performing, by a device operatively coupled to a processor, using a library of templates comprising gates, template matching on a Clifford circuit associated with a set of qubits; and
partitioning, by the device and prior to the template matching, the Clifford circuit into a computation stage, a Pauli stage, and a SWAP stage, wherein the template matching is performed on the computation stage, and wherein:
the computation state comprises all Hadamard gates, all Phase gates, and all Controlled NOT gates of the Clifford circuit, and does not comprise any Pauli gates and any SWAP gates of the Clifford circuit;
the Pauli stage comprises all Pauli gates of the Clifford circuit, and does not comprise any Hadamard gates, any Phase gates, any Controlled NOT gates, and any SWAP gates of the Clifford circuit; and
the SWAP stage comprises all SWAP gates of the Clifford circuit, and does not comprise any Hadamard gates, any Phase gates, any Controlled NOT gates, and any Pauli gates of the Clifford circuit.

10. The computer-implemented method of claim 9 , further comprising:
pushing, by the device, a blocking gate out of a template matching range in the computation stage by replacing the blocking gate with a linear combination of Pauli gates.

11. The computer-implemented method of claim 9 , further comprising:
re-partitioning, by the device, the Clifford circuit when performance of the template matching in the computation stage yields a Pauli gate or a SWAP gate in the computation stage.

12. The computer-implemented method of claim 9 , further comprising:
selecting, by the device, a subset of qubits from the set of qubits;
rewiring, by the device, at least one entangling gate in the computation stage such that a target of the at least one entangling gate is in the subset of qubits; and
replacing, by the device, the at least one rewired entangling gate with a symbolic Pauli gate, wherein the symbolic Pauli gate is a Pauli gate that is controlled by a symbolic variable.

13. The computer-implemented method of claim 12 , further comprising:
performing, by the device, peephole optimization on the subset of qubits with the symbolic Pauli gate by implementing a dynamic programming algorithm.

14. The computer-implemented method of claim 9 , wherein the performing the template matching comprises, in response to determining that the Clifford circuit is optimized with respect to two-qubit gate count, restricting the template matching to a subset of the templates that can reduce single-qubit gate count without also reducing the two-bit gate count.

15. The computer-implemented method of claim 14 , wherein the subset of the templates comprises at least one of single-qubit templates or templates with an even number of two-bit gates.

16. A computer program product for facilitating partitioned template matching and symbolic peephole optimization, the computer program product comprising a non-transitory computer readable medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
perform, by the processor, using a library of templates comprising gates, template matching on a Clifford circuit associated with a set of qubits; and
partition, by the processor and prior to the template matching, the Clifford circuit into a computation stage, a Pauli stage, and a SWAP stage, wherein the template matching is performed on the computation stage, and wherein:
the computation state comprises all Hadamard gates, all Phase gates, and all Controlled NOT gates of the Clifford circuit, and does not comprise any Pauli gates and any SWAP gates of the Clifford circuit;
the Pauli stage comprises all Pauli gates of the Clifford circuit, and does not comprise any Hadamard gates, any Phase gates, any Controlled NOT gates, and any SWAP gates of the Clifford circuit; and
the SWAP stage comprises all SWAP gates of the Clifford circuit, and does not comprise any Hadamard gates, any Phase gates, any Controlled NOT gates, and any Pauli gates of the Clifford circuit.

17. The computer program product of claim 16 , wherein the program instructions are further executable to cause the processor to:
push, by the processor, a blocking gate out of a template matching range in the computation stage by replacing the blocking gate with a linear combination of Pauli gates.

18. The computer program product of claim 16 , wherein the program instructions are further executable to cause the processor to:
re-partition, by the processor, the Clifford circuit when performance of the template matching in the computation stage yields a Pauli gate or a SWAP gate in the computation stage.

19. The computer program

Assignees

• IBM

Inventors

• Bravyi Sergey
• Hu Shaohan
• Maslov Dmitri
• Shaydulin Ruslan

Classifications

• G06F30/323

  Translation or migration, e.g. logic to logic, hardware description language [HDL] translation or netlist translation · CPC title

• G06N10/80

  Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing · CPC title

• G06N10/20 Primary

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

• G06N10/00

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

• G06F30/3308

  using simulation · CPC title