0
# Algorithm Synthesis
1

2
Qiskit's synthesis module provides advanced algorithms for decomposing and constructing quantum circuits, including Clifford synthesis, permutation synthesis, and quantum algorithm primitives.
3

4
## Capabilities
5

6
### Clifford Synthesis
7

8
```python { .api }
9
def synth_clifford_full(clifford, method='AG'):
10
    """Synthesize Clifford operator into elementary gates."""
11

12
def synth_clifford_ag(clifford):
13
    """Aaronson-Gottesman Clifford synthesis."""
14

15
def synth_clifford_bm(clifford):
16
    """Bravyi-Maslov Clifford synthesis."""
17

18
def synth_clifford_greedy(clifford):
19
    """Greedy Clifford synthesis."""
20

21
def synth_clifford_layers(clifford, cx_synth_func=None, cz_synth_func=None):
22
    """Layer-by-layer Clifford synthesis."""
23
```
24

25
### CNOT and Linear Synthesis
26

27
```python { .api }
28
def synth_cnot_count_full_pmh(state):
29
    """CNOT synthesis using PMH algorithm."""
30

31
def synth_cnot_depth_line_kms(state):
32
    """Linear topology CNOT synthesis."""
33

34
def synth_linear_depth_5_from_matrix(matrix):
35
    """Synthesize linear function with depth 5."""
36
```
37

38
### Permutation Synthesis
39

40
```python { .api }
41
def synth_permutation_depth_lnn_kms(pattern):
42
    """KMS permutation synthesis for linear topology."""
43

44
def synth_permutation_basic(pattern):
45
    """Basic permutation synthesis."""
46

47
def synth_permutation_acg(pattern):
48
    """ACG permutation synthesis algorithm."""
49
```
50

51
### Pauli Evolution Synthesis
52

53
```python { .api }
54
class LieTrotter:
55
    def __init__(self, reps=1):
56
        """Lie-Trotter decomposition for Hamiltonian evolution."""
57

58
class SuzukiTrotter:
59
    def __init__(self, order, reps=1):
60
        """Suzuki-Trotter decomposition methods."""
61

62
class MatrixExponential:
63
    def __init__(self):
64
        """Direct matrix exponential method."""
65

66
class QDrift:
67
    def __init__(self, reps=1):
68
        """QDrift Hamiltonian evolution algorithm."""
69
```
70

71
### Stabilizer Synthesis
72

73
Synthesis algorithms for stabilizer circuits and states.
74

75
```python { .api }
76
def synth_stabilizer_layers(stab_state, cz_synth_func=None, 
77
                           cx_synth_func=None, validate=True):
78
    """
79
    Synthesize stabilizer state using layered approach.
80
    
81
    Parameters:
82
    - stab_state: Stabilizer state to synthesize
83
    - cz_synth_func: Function for CZ synthesis
84
    - cx_synth_func: Function for CX synthesis  
85
    - validate: Whether to validate stabilizer state
86
    """
87

88
def synth_stabilizer_depth_lnn(stab_state):
89
    """
90
    Depth-optimal stabilizer synthesis for linear topology.
91
    
92
    Parameters:
93
    - stab_state: Stabilizer state to synthesize
94
    """
95

96
def synth_circuit_from_stabilizers(stabilizers, allow_redundant=True):
97
    """
98
    Synthesize circuit from stabilizer generators.
99
    
100
    Parameters:
101
    - stabilizers: List of stabilizer generators
102
    - allow_redundant: Whether to allow redundant stabilizers
103
    """
104
```
105

106
### Multi-Controlled Gate Synthesis
107

108
Synthesis of multi-controlled quantum gates using various decomposition strategies.
109

110
```python { .api }
111
def synth_mcx_n_dirty_i15(num_ctrl_qubits, num_dirty_qubits):
112
    """
113
    Multi-controlled X gate using dirty ancillas.
114
    
115
    Parameters:
116
    - num_ctrl_qubits: Number of control qubits
117
    - num_dirty_qubits: Number of dirty ancilla qubits
118
    """
119

120
def synth_mcx_n_clean_m15(num_ctrl_qubits, num_clean_qubits):
121
    """
122
    Multi-controlled X gate using clean ancillas.
123
    
124
    Parameters:
125
    - num_ctrl_qubits: Number of control qubits
126
    - num_clean_qubits: Number of clean ancilla qubits
127
    """
128

129
def synth_mcx_gray_code(num_ctrl_qubits):
130
    """
131
    Multi-controlled X gate using Gray code sequence.
132
    
133
    Parameters:
134
    - num_ctrl_qubits: Number of control qubits
135
    """
136

137
def synth_mcx_noaux_v24(num_ctrl_qubits):
138
    """
139
    Multi-controlled X gate without ancilla qubits.
140
    
141
    Parameters:
142
    - num_ctrl_qubits: Number of control qubits
143
    """
144
```
145

146
### Unitary Synthesis
147

148
Advanced synthesis algorithms for arbitrary unitary matrices.
149

150
```python { .api }
151
def qs_decomposition(unitary, opt_a1=True, opt_a2=True, decomp_gate=None):
152
    """
153
    Quantum Shannon decomposition of unitary matrices.
154
    
155
    Parameters:
156
    - unitary: Unitary matrix to decompose
157
    - opt_a1: Optimize A1 gate
158
    - opt_a2: Optimize A2 gate  
159
    - decomp_gate: Decomposition gate type
160
    """
161

162
class OneQubitEulerDecomposer:
163
    def __init__(self, basis='ZYZ', use_dag=False):
164
        """
165
        Single-qubit unitary decomposer.
166
        
167
        Parameters:
168
        - basis: Euler rotation basis ('ZYZ', 'ZXZ', 'XYX', 'ZYX')
169
        - use_dag: Whether to use DAG representation
170
        """
171

172
class TwoQubitBasisDecomposer:
173
    def __init__(self, gate, basis_fidelity=1.0, euler_basis=None):
174
        """
175
        Two-qubit gate decomposer.
176
        
177
        Parameters:
178
        - gate: Target two-qubit gate
179
        - basis_fidelity: Fidelity of basis gate
180
        - euler_basis: Single-qubit Euler basis
181
        """
182

183
class XXDecomposer:
184
    def __init__(self, embodiments=None):
185
        """
186
        Decomposer for XX(theta) gates.
187
        
188
        Parameters:
189
        - embodiments: Available gate embodiments
190
        """
191
```
192

193
### Discrete Basis Synthesis
194

195
Solovay-Kitaev algorithm for discrete gate set approximation.
196

197
```python { .api }
198
class SolovayKitaevDecomposition:
199
    def __init__(self, basic_approximations=None, depth=10):
200
        """
201
        Solovay-Kitaev algorithm implementation.
202
        
203
        Parameters:
204
        - basic_approximations: Pre-computed gate approximations
205
        - depth: Recursion depth for approximation
206
        """
207

208
def generate_basic_approximations(gate_set, depth=10, filename=None):
209
    """
210
    Generate basic approximations for Solovay-Kitaev.
211
    
212
    Parameters:
213
    - gate_set: Set of discrete gates
214
    - depth: Maximum sequence depth
215
    - filename: File to save approximations
216
    """
217
```
218

219
### Usage Examples
220

221
```python
222
from qiskit.synthesis import *
223
from qiskit.quantum_info import Clifford, random_clifford
224

225
# Clifford synthesis
226
clifford = random_clifford(3)
227
circuit = synth_clifford_full(clifford)
228

229
# Permutation synthesis
230
pattern = [2, 1, 0]  # Reverse 3 qubits
231
perm_circuit = synth_permutation_basic(pattern)
232

233
# Pauli evolution
234
from qiskit.quantum_info import SparsePauliOp
235
hamiltonian = SparsePauliOp.from_list([('ZZ', 1.0), ('XX', 0.5)])
236
evolution = LieTrotter(reps=4)
237
```