GateMergeOptimizer.cpp 12 KB
Newer Older
1
#include <cassert>
2
3
4
#include "GateMergeOptimizer.hpp"
#include "GateFusion.hpp"
#include "xacc_service.hpp"
5
6
7
8
9

namespace xacc {
namespace quantum {
void MergeSingleQubitGatesOptimizer::apply(std::shared_ptr<CompositeInstruction> program, const std::shared_ptr<Accelerator> accelerator, const HeterogeneousMap &options)
{
10
    auto gateRegistry = xacc::getService<xacc::IRProvider>("quantum");
11
12
    for (size_t instIdx = 0; instIdx < program->nInstructions(); ++instIdx)
    {
13
        const auto sequence = findSingleQubitGateSequence(program, instIdx, 2);
14
15
        if (!sequence.empty()) 
        {
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
            auto tmpKernel = gateRegistry->createComposite("__TMP__");
            for (const auto& instIdx: sequence)
            {
                auto instrPtr = program->getInstruction(instIdx)->clone();
                assert(instrPtr->bits().size() == 1);
                // Remap to bit 0 for fusing
                instrPtr->setBits({ 0 });
                tmpKernel->addInstruction(instrPtr);
            }

            auto fuser = xacc::getService<xacc::quantum::GateFuser>("default");
            fuser->initialize(tmpKernel);
            const Eigen::Matrix2cd uMat = fuser->calcFusedGate(1);
            auto zyz = std::dynamic_pointer_cast<quantum::Circuit>(xacc::getService<Instruction>("z-y-z"));
            const bool expandOk = zyz->expand({ 
                std::make_pair("unitary", uMat)
            });
33
            assert(expandOk);
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
            // Optimized decomposed sequence:
            const auto nbInstructionsAfter = zyz->nInstructions();
            // A simplified sequence was found.
            if (nbInstructionsAfter < sequence.size())
            {
                // Rewrite:
                const size_t bitIdx = program->getInstruction(sequence[0])->bits()[0];
                // Disable to remove:
                const auto programLengthBefore = program->nInstructions();
                for (const auto& instIdx: sequence)
                {
                    auto instrPtr = program->getInstruction(instIdx);
                    instrPtr->disable();
                }
                program->removeDisabled();
                const auto locationToInsert = sequence[0];
                for (auto& newInst: zyz->getInstructions())
                {
                    newInst->setBits({bitIdx});
                    program->insertInstruction(locationToInsert, newInst->clone());
                }
                const auto programLengthAfter = program->nInstructions();
                assert(programLengthAfter < programLengthBefore);
            }
58
59
60
61
        }
    }
}

62
std::vector<size_t> MergeSingleQubitGatesOptimizer::findSingleQubitGateSequence(const std::shared_ptr<CompositeInstruction> in_program, size_t in_startIdx, size_t in_lengthLimit) const
63
64
{
    const auto nbInstructions = in_program->nInstructions();
65
66
67
68
    assert(in_startIdx < nbInstructions);
    auto firstInst = in_program->getInstruction(in_startIdx);
    // Not a single-qubit gate.
    if (firstInst->bits().size() > 1 || firstInst->name() == "Measure")
69
    {
70
71
        return {};
    }
72

73
74
75
76
77
78
79
80
81
82
83
84
85
    const size_t bitIdx = firstInst->bits()[0];
    std::vector<size_t> gateSequence;
    gateSequence.emplace_back(in_startIdx);

    const auto returnSeq = [&](const std::vector<size_t>& in_seq) -> std::vector<size_t> {
        return (in_seq.size() >= in_lengthLimit) ? in_seq : std::vector<size_t>{};
    };

    for (size_t instIdx = in_startIdx + 1; instIdx < nbInstructions; ++instIdx)
    {
        auto instPtr = in_program->getInstruction(instIdx);
        // Matching bitIdx
        if (instPtr->bits().size() == 1 && instPtr->bits()[0] == bitIdx)
86
        {
87
            if (instPtr->name() != "Measure")
88
            {
89
                gateSequence.emplace_back(instIdx);
90
            }
91
            else 
92
            {
93
                return returnSeq(gateSequence);
94
95
            }
        }
96
97
98
        // If this is a two-qubit gate that involves this qubit wire,
        // terminate the scan and return.
        else if (instPtr->bits().size() == 2 && xacc::container::contains(instPtr->bits(), bitIdx))
99
        {
100
            return returnSeq(gateSequence);
101
        }
102
103
104
    }  
    // Reach the end of the circuit:  
    return returnSeq(gateSequence);    
105
}
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300

void MergeTwoQubitBlockOptimizer::apply(std::shared_ptr<CompositeInstruction> program, const std::shared_ptr<Accelerator> accelerator, const HeterogeneousMap& options)
{
    auto gateRegistry = xacc::getService<xacc::IRProvider>("quantum");

    // No need to optimize block with less than 6 gates
    // since the KAK decomposition will result in at least 5 gate.
    const size_t MIN_SIZE = 6;
    if (program->nInstructions() < MIN_SIZE)
    {
        return;
    }
    for (size_t instIdx = 0; instIdx < program->nInstructions(); ++instIdx)
    {
        std::pair<size_t, size_t> qubitPair = std::make_pair(0, 0);
        const auto sequence = findGateSequence(program, instIdx, MIN_SIZE, qubitPair);
        if (!sequence.empty()) 
        {
            auto tmpKernel = gateRegistry->createComposite("__TMP__");
            
            const auto mapBits = [&qubitPair](const std::vector<size_t>& in_bits){
                const auto translate = [&qubitPair](size_t bit) {
                    assert(bit == qubitPair.first || bit == qubitPair.second);
                    assert(qubitPair.first  != qubitPair.second);
                    if (qubitPair.first < qubitPair.second)
                    {
                        return (bit == qubitPair.first) ? 0 : 1;
                    }
                    else
                    {
                        return (bit == qubitPair.first) ? 1 : 0;
                    }
                }; 

                std::vector<size_t> newBits;
                for (const auto& bit: in_bits)         
                {
                    newBits.emplace_back(translate(bit));
                }   
                return newBits;
            };

            // Map { 0, 1 } bits back to original bits
            const auto remapBits = [&qubitPair](const std::vector<size_t>& in_bits){
                const auto translate = [&qubitPair](size_t bit) {
                    assert(bit == 0 || bit == 1);
                    assert(qubitPair.first  != qubitPair.second);
                    if (qubitPair.first < qubitPair.second)
                    {
                        return (bit == 0) ? qubitPair.first : qubitPair.second;
                    }
                    else
                    {
                        return (bit == 0) ? qubitPair.second : qubitPair.first;
                    }
                }; 

                std::vector<size_t> newBits;
                for (const auto& bit: in_bits)         
                {
                    newBits.emplace_back(translate(bit));
                }   
                return newBits;
            };

            for (const auto& instIdx: sequence)
            {
                auto instrPtr = program->getInstruction(instIdx)->clone();
                instrPtr->setBits(mapBits(instrPtr->bits()));
                tmpKernel->addInstruction(instrPtr);
            }
            auto fuser = xacc::getService<xacc::quantum::GateFuser>("default");
            fuser->initialize(tmpKernel);
            const Eigen::Matrix4cd uMat = fuser->calcFusedGate(2);
            auto kak = std::dynamic_pointer_cast<quantum::Circuit>(xacc::getService<Instruction>("kak"));
            const bool expandOk = kak->expand({ 
                std::make_pair("unitary", uMat)
            });
            assert(expandOk);

            // Optimized decomposed sequence:
            const auto nbInstructionsAfter = kak->nInstructions();
            // A simplified sequence was found.
            if (nbInstructionsAfter < sequence.size())
            {
                // Disable to remove:
                const auto programLengthBefore = program->nInstructions();
                for (const auto& instIdx: sequence)
                {
                    auto instrPtr = program->getInstruction(instIdx);
                    instrPtr->disable();
                }
                program->removeDisabled();

                const auto locationToInsert = sequence[0];
                for (auto& newInst: kak->getInstructions())
                {
                    newInst->setBits(remapBits(newInst->bits()));
                    program->insertInstruction(locationToInsert, newInst->clone());
                }
                const auto programLengthAfter = program->nInstructions();
                assert(programLengthAfter < programLengthBefore);
            }
        }
    }
}

std::vector<size_t> MergeTwoQubitBlockOptimizer::findGateSequence(const std::shared_ptr<CompositeInstruction> in_program, size_t in_startIdx, size_t in_lengthLimit, std::pair<size_t, size_t>& out_qubitPair) const
{
    const auto nbInstructions = in_program->nInstructions();
    assert(in_startIdx < nbInstructions);
    auto firstInst = in_program->getInstruction(in_startIdx);
    if (firstInst->name() == "Measure")
    {
        return {};
    }

    const auto qubitPairIfAny = [&]() -> std::optional<std::pair<size_t, size_t>> {
        if (firstInst->bits().size() == 2)
        {
            return std::make_pair(firstInst->bits()[0], firstInst->bits()[1]);
        }

        // Single qubit gate:
        // Scan forward to find the *first* two-qubit gate which involves this qubit.
        assert(firstInst->bits().size() == 1);
        const auto firstBitIdx =  firstInst->bits()[0];
        for (size_t instIdx = in_startIdx + 1; instIdx < nbInstructions; ++instIdx)
        {
            auto instPtr = in_program->getInstruction(instIdx);
            if (instPtr->bits().size() == 2 && xacc::container::contains(instPtr->bits(), firstBitIdx))
            {
                return std::make_pair(instPtr->bits()[0], instPtr->bits()[1]);
            }
        }
        // Cannot find the boundary: i.e. no two-qubit gates
        return std::optional<std::pair<size_t, size_t>>();
    }();

    if (!qubitPairIfAny.has_value())
    {
        return {};
    }
    const auto qubitPair = qubitPairIfAny.value();
    std::vector<size_t> gateSequence;
    gateSequence.emplace_back(in_startIdx);
    out_qubitPair = qubitPair;
    const auto returnSeq = [&](const std::vector<size_t>& in_seq) -> std::vector<size_t> {
        return (in_seq.size() >= in_lengthLimit) ? in_seq : std::vector<size_t>{};
    };

    for (size_t instIdx = in_startIdx + 1; instIdx < nbInstructions; ++instIdx)
    {
        auto instPtr = in_program->getInstruction(instIdx);
        if (instPtr->bits().size() == 1)
        {
            if (instPtr->bits()[0] == qubitPair.first || instPtr->bits()[0] == qubitPair.second)
            {
                if (instPtr->name() == "Measure")
                {
                    return returnSeq(gateSequence);
                }
                else
                {
                    gateSequence.emplace_back(instIdx);
                }
            }
        }
        else if (instPtr->bits().size() == 2)
        {
            const auto areQubitOperandsMatched = [&qubitPair](const std::vector<size_t>& in_bits) {
                const bool match1 =  (in_bits[0] == qubitPair.first) && (in_bits[1] == qubitPair.second); 
                const bool match2 =  (in_bits[1] == qubitPair.first) && (in_bits[0] == qubitPair.second); 
                return match1 || match2;
            };

            const auto hasOnlyOneBitMatched = [&qubitPair](const std::vector<size_t>& in_bits) {
                const bool oneMatched = xacc::container::contains(in_bits, qubitPair.first) || xacc::container::contains(in_bits, qubitPair.second);
                const bool oneNotMatched = !xacc::container::contains(in_bits, qubitPair.first) || !xacc::container::contains(in_bits, qubitPair.second);
                return oneMatched && oneNotMatched;
            };

            if (areQubitOperandsMatched(instPtr->bits()))
            {
                gateSequence.emplace_back(instIdx);
            }
            else if (hasOnlyOneBitMatched(instPtr->bits()))
            {
                return returnSeq(gateSequence);
            }
        }
    }
    // End of circuit:
    return returnSeq(gateSequence);
}
301
302
}
}