GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billt/mac-intel-cryptography

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/library/chemistry/src/JordanWigner

library/chemistry/src/JordanWigner/OptimizedBlockEncoding.qs

787lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4export OptimizedBETermIndex;
5export OptimizedBEGeneratorSystem;
6export OptimizedBlockEncodingGeneratorSystem;
7export MixedStatePreparation;
8export BlockEncodingByLCU;
9export QuantumWalkByQubitization;
10export PauliBlockEncoding;
11
12import Std.Arrays.*;
13import Std.Math.*;
14import Std.Convert.IntAsDouble;
15import Std.Arithmetic.ApplyIfGreaterLE;
16import Std.StatePreparation.PreparePureStateD;
17import Std.Diagnostics.Fact;
18
19import Generators.GeneratorIndex;
20import Generators.GeneratorSystem;
21import Generators.HTermToGenIdx;
22import Generators.MultiplexOperationsFromGenerator;
23import JordanWigner.OptimizedBEOperator.JWSelect;
24import JordanWigner.OptimizedBEOperator.JWSelectQubitCount;
25import JordanWigner.OptimizedBEOperator.JWSelectQubitManager;
26import JordanWigner.Data.JWOptimizedHTerms;
27import MixedStatePreparation.PurifiedMixedState;
28import MixedStatePreparation.PurifiedMixedStateRequirements;
29import Utils.RangeAsIntArray;
30import Utils.IsNotZero;
31
32/// # Summary
33/// Term data in the optimized block-encoding algorithm.
34struct OptimizedBETermIndex {
35 Coefficient : Double,
36 UseSignQubit : Bool,
37 ZControlRegisterMask : Bool[],
38 OptimizedControlRegisterMask : Bool[],
39 PauliBases : Int[],
40 RegisterIndices : Int[],
41}
42
43/// # Summary
44/// Function that returns `OptimizedBETermIndex` data for term `n` given an
45/// integer `n`, together with the number of terms in the first `Int` and
46/// the sum of absolute-values of all term coefficients in the `Double`.
47struct OptimizedBEGeneratorSystem {
48 NumTerms : Int,
49 Norm : Double,
50 SelectTerm : (Int -> OptimizedBETermIndex)
51}
52
53function JWOptimizedBlockEncoding(
54 targetError : Double,
55 data : JWOptimizedHTerms,
56 nSpinOrbitals : Int
57) : ((Int, Int), (Double, (Qubit[], Qubit[]) => Unit is Adj + Ctl)) {
58
59 let nZ = 2;
60 let nMaj = 4;
61 let optimizedBEGeneratorSystem = OptimizedBlockEncodingGeneratorSystem(data);
62 let nCoeffs = optimizedBEGeneratorSystem.NumTerms;
63 let nIdxRegQubits = Ceiling(Lg(IntAsDouble(nSpinOrbitals)));
64 let ((nCtrlRegisterQubits, nTargetRegisterQubits), rest) = JWOptimizedBlockEncodingQubitCount(
65 targetError,
66 nCoeffs,
67 nZ,
68 nMaj,
69 nIdxRegQubits,
70 nSpinOrbitals
71 );
72 let statePrepOp = JWOptimizedBlockEncodingStatePrepWrapper(
73 targetError,
74 nCoeffs,
75 optimizedBEGeneratorSystem,
76 nZ,
77 nMaj,
78 nIdxRegQubits,
79 _
80 );
81 let selectOp = JWOptimizedBlockEncodingSelect(
82 targetError,
83 nCoeffs,
84 optimizedBEGeneratorSystem,
85 nZ,
86 nMaj,
87 nIdxRegQubits,
88 _,
89 _
90 );
91 let blockEncodingReflection = BlockEncodingByLCU(statePrepOp, selectOp);
92 return (
93 (nCtrlRegisterQubits, nTargetRegisterQubits),
94 (optimizedBEGeneratorSystem.Norm, blockEncodingReflection)
95 );
96}
97
98// Get OptimizedBEGeneratorSystem coefficients
99function OptimizedBEGeneratorSystemCoeff(optimizedBEGeneratorSystem : OptimizedBEGeneratorSystem) : Double[] {
100 mutable coefficients = [];
101 for idx in 0..optimizedBEGeneratorSystem.NumTerms - 1 {
102 coefficients += [optimizedBEGeneratorSystem.SelectTerm(idx).Coefficient];
103 }
104 return coefficients;
105}
106
107
108/// # Summary
109/// Converts a `GeneratorIndex` describing a Z term to
110/// an expression `GeneratorIndex[]` in terms of Paulis.
111///
112/// # Input
113/// ## term
114/// `GeneratorIndex` representing a Z term.
115///
116/// # Output
117/// `OptimizedBETermIndex` expressing Z term as Pauli terms.
118function ZTermToPauliMajIdx(term : GeneratorIndex) : OptimizedBETermIndex {
119 let (_, coeff) = term.Term;
120 let idxFermions = term.Subsystem;
121 let signQubit = coeff[0] < 0.0;
122 let selectZControlRegisters = [true];
123 let optimizedBEControlRegisters = [];
124 let pauliBases = [];
125 let indexRegisters = idxFermions;
126 return new OptimizedBETermIndex {
127 Coefficient = coeff[0],
128 UseSignQubit = signQubit,
129 ZControlRegisterMask = selectZControlRegisters,
130 OptimizedControlRegisterMask = optimizedBEControlRegisters,
131 PauliBases = pauliBases,
132 RegisterIndices = indexRegisters
133 };
134}
135
136
137/// # Summary
138/// Converts a GeneratorIndex describing a ZZ term to
139/// an expression `GeneratorIndex[]` in terms of Paulis.
140///
141/// # Input
142/// ## term
143/// `GeneratorIndex` representing a ZZ term.
144///
145/// # Output
146/// `OptimizedBETermIndex` expressing ZZ term as Pauli terms.
147function ZZTermToPauliMajIdx(term : GeneratorIndex) : OptimizedBETermIndex {
148 let (_, coeff) = term.Term;
149 let idxFermions = term.Subsystem;
150 let signQubit = coeff[0] < 0.0;
151 let selectZControlRegisters = [true, true];
152 let optimizedBEControlRegisters = [];
153 let pauliBases = [];
154 let indexRegisters = idxFermions;
155 return new OptimizedBETermIndex {
156 Coefficient = 2.0 * coeff[0],
157 UseSignQubit = signQubit,
158 ZControlRegisterMask = selectZControlRegisters,
159 OptimizedControlRegisterMask = optimizedBEControlRegisters,
160 PauliBases = pauliBases,
161 RegisterIndices = indexRegisters
162 };
163}
164
165
166/// # Summary
167/// Converts a `GeneratorIndex` describing a PQ term to
168/// an expression `GeneratorIndex[]` in terms of Paulis
169///
170/// # Input
171/// ## term
172/// `GeneratorIndex` representing a PQ term.
173///
174/// # Output
175/// `OptimizedBETermIndex` expressing PQ term as Pauli terms.
176function PQTermToPauliMajIdx(term : GeneratorIndex) : OptimizedBETermIndex {
177 let (_, coeff) = term.Term;
178 let idxFermions = term.Subsystem;
179 let sign = coeff[0] < 0.0;
180 let selectZControlRegisters = [];
181 let optimizedBEControlRegisters = [true, true];
182 let pauliBases = [1, 2];
183 let indexRegisters = idxFermions;
184 return new OptimizedBETermIndex {
185 Coefficient = 2.0 * coeff[0],
186 UseSignQubit = sign,
187 ZControlRegisterMask = selectZControlRegisters,
188 OptimizedControlRegisterMask = optimizedBEControlRegisters,
189 PauliBases = pauliBases,
190 RegisterIndices = indexRegisters
191 };
192}
193
194
195/// # Summary
196/// Converts a `GeneratorIndex` describing a PQ or PQQR term to
197/// an expression `GeneratorIndex[]` in terms of Paulis
198///
199/// # Input
200/// ## term
201/// `GeneratorIndex` representing a PQ or PQQR term.
202///
203/// # Output
204/// `OptimizedBETermIndex` expressing PQ or PQQR term as Pauli terms.
205function PQandPQQRTermToPauliMajIdx(term : GeneratorIndex) : OptimizedBETermIndex {
206 let (_, coeff) = term.Term;
207 let idxFermions = term.Subsystem;
208 let sign = coeff[0] < 0.0;
209
210 if Length(idxFermions) == 2 {
211 return PQTermToPauliMajIdx(term);
212 } else {
213 let qubitPidx = idxFermions[0];
214 let qubitQidx = idxFermions[1];
215 let qubitRidx = idxFermions[3];
216 let selectZControlRegisters = [false, true];
217 let optimizedBEControlRegisters = [true, false, true];
218 let pauliBases = [1, 2];
219 let indexRegisters = [qubitPidx, qubitQidx, qubitRidx];
220 return new OptimizedBETermIndex {
221 Coefficient = 2.0 * coeff[0],
222 UseSignQubit = sign,
223 ZControlRegisterMask = selectZControlRegisters,
224 OptimizedControlRegisterMask = optimizedBEControlRegisters,
225 PauliBases = pauliBases,
226 RegisterIndices = indexRegisters
227 };
228 }
229}
230
231
232/// # Summary
233/// Converts a `GeneratorIndex` describing a PQRS term to
234/// an expression `GeneratorIndex[]` in terms of Paulis
235///
236/// # Input
237/// ## term
238/// `GeneratorIndex` representing a PQRS term.
239///
240/// # Output
241/// `OptimizedBETermIndex[]` expressing PQRS term as Pauli terms.
242function V0123TermToPauliMajIdx(term : GeneratorIndex) : OptimizedBETermIndex[] {
243 let (_, v0123) = term.Term;
244 let idxFermions = term.Subsystem;
245 let qubitsPQ = idxFermions[0..1];
246 let qubitsRS = idxFermions[2..3];
247 let qubitsPQJW = RangeAsIntArray(qubitsPQ[0] + 1..qubitsPQ[1] - 1);
248 let qubitsRSJW = RangeAsIntArray(qubitsRS[0] + 1..qubitsRS[1] - 1);
249 let ops = [
250 [1, 1, 1, 1],
251 [1, 1, 2, 2],
252 [1, 2, 1, 2],
253 [1, 2, 2, 1],
254 [2, 2, 2, 2],
255 [2, 2, 1, 1],
256 [2, 1, 2, 1],
257 [2, 1, 1, 2]
258 ];
259 mutable majIdxes = Repeated(
260 new OptimizedBETermIndex {
261 Coefficient = 0.0,
262 UseSignQubit = false,
263 ZControlRegisterMask = [],
264 OptimizedControlRegisterMask = [],
265 PauliBases = [],
266 RegisterIndices = []
267 },
268 4
269 );
270 mutable nonZero = 0;
271 let selectZControlRegisters = [];
272 let optimizedBEControlRegisters = [true, true, true, true];
273 let indexRegisters = idxFermions;
274
275 for idxOp in 0..3 {
276 if IsNotZero(v0123[idxOp]) {
277 let newCoeff = (2.0 * 0.25) * v0123[idxOp];
278 majIdxes w/= nonZero <- new OptimizedBETermIndex {
279 Coefficient = newCoeff,
280 UseSignQubit = v0123[idxOp] < 0.0,
281 ZControlRegisterMask = selectZControlRegisters,
282 OptimizedControlRegisterMask = optimizedBEControlRegisters,
283 PauliBases = ops[idxOp],
284 RegisterIndices = indexRegisters
285 };
286 nonZero = nonZero + 1;
287 }
288 }
289
290 return majIdxes[0..nonZero - 1];
291}
292
293
294/// # Summary
295/// Converts a Hamiltonian described by `JWOptimizedHTerms`
296/// to a `GeneratorSystem` expressed in terms of the Pauli
297/// `GeneratorIndex`.
298///
299/// # Input
300/// ## data
301/// Description of Hamiltonian in `JWOptimizedHTerms` format.
302///
303/// # Output
304/// Representation of Hamiltonian as `GeneratorSystem`.
305function OptimizedBlockEncodingGeneratorSystem(data : JWOptimizedHTerms) : OptimizedBEGeneratorSystem {
306 let ZData = data.HTerm0;
307 let ZZData = data.HTerm1;
308 let PQandPQQRData = data.HTerm2;
309 let h0123Data = data.HTerm3;
310 mutable majIdxes = Repeated(
311 new OptimizedBETermIndex {
312 Coefficient = 0.0,
313 UseSignQubit = false,
314 ZControlRegisterMask = [],
315 OptimizedControlRegisterMask = [],
316 PauliBases = [],
317 RegisterIndices = []
318 },
319 ((Length(ZData) + Length(ZZData)) + Length(PQandPQQRData)) + 4 * Length(h0123Data)
320 );
321 mutable startIdx = 0;
322
323 for idx in IndexRange(ZData) {
324 // Array of Arrays of Length 1
325 majIdxes w/= idx <- ZTermToPauliMajIdx(HTermToGenIdx(ZData[idx], [0]));
326 }
327
328 startIdx = Length(ZData);
329
330 for idx in IndexRange(ZZData) {
331 // Array of Arrays of Length 1
332 majIdxes w/= startIdx + idx <- ZZTermToPauliMajIdx(HTermToGenIdx(ZZData[idx], [1]));
333 }
334
335 startIdx = startIdx + Length(ZZData);
336
337 for idx in IndexRange(PQandPQQRData) {
338
339 // Array of Arrays of Length 1
340 majIdxes w/= startIdx + idx <- PQandPQQRTermToPauliMajIdx(HTermToGenIdx(PQandPQQRData[idx], [2]));
341 }
342
343 startIdx = startIdx + Length(PQandPQQRData);
344 mutable finalIdx = startIdx;
345
346 for idx in 0..Length(h0123Data) - 1 {
347
348 // Array of Arrays of Length up to 4
349 let genArr = V0123TermToPauliMajIdx(HTermToGenIdx(h0123Data[idx], [3]));
350
351 for idx0123 in IndexRange(genArr) {
352 majIdxes w/= finalIdx <- genArr[idx0123];
353 finalIdx = finalIdx + 1;
354 }
355 }
356
357 mutable oneNorm = 0.0;
358
359 for idx in 0..finalIdx - 1 {
360 oneNorm = oneNorm + AbsD(majIdxes[idx].Coefficient);
361 }
362
363 let majIdxes = majIdxes[0..finalIdx - 1];
364 return new OptimizedBEGeneratorSystem {
365 NumTerms = finalIdx,
366 Norm = oneNorm,
367 SelectTerm = idx -> majIdxes[idx]
368 };
369}
370
371
372operation ToJWSelectInput(
373 idx : Int,
374 optimizedBEGeneratorSystem : OptimizedBEGeneratorSystem,
375 signQubit : Qubit,
376 selectZControlRegisters : Qubit[],
377 optimizedBEControlRegisters : Qubit[],
378 pauliBasesIdx : Qubit[],
379 indexRegisters : Qubit[][]
380) : Unit is Adj + Ctl {
381 let optimizedBETermIndex = optimizedBEGeneratorSystem.SelectTerm(idx);
382
383 // Write bit to apply - signQubit
384 if optimizedBETermIndex.UseSignQubit {
385 X(signQubit);
386 }
387
388 // Write bit to activate selectZ operator
389 let selectZControlRegistersSet = optimizedBETermIndex.ZControlRegisterMask;
390 for i in IndexRange(selectZControlRegistersSet) {
391 if selectZControlRegistersSet[i] {
392 X(selectZControlRegisters[i]);
393 }
394 }
395
396 // Write bit to activate OptimizedBEXY operator
397 let optimizedBEControlRegistersSet = optimizedBETermIndex.OptimizedControlRegisterMask;
398 for i in IndexRange(optimizedBEControlRegistersSet) {
399 if optimizedBEControlRegistersSet[i] {
400 X(optimizedBEControlRegisters[i]);
401 }
402 }
403
404 // Write bitstring to apply desired XZ... or YZ... Pauli string
405 let indexRegistersSet = optimizedBETermIndex.RegisterIndices;
406 for i in IndexRange(indexRegistersSet) {
407 ApplyXorInPlace(indexRegistersSet[i], indexRegisters[i]);
408 }
409
410 // Crete state to select uniform superposition of X and Y operators.
411 let pauliBasesSet = optimizedBETermIndex.PauliBases;
412 if Length(pauliBasesSet) == 2 {
413 // for PQ or PQQR terms, create |00> + |11>
414 ApplyXorInPlace(0, pauliBasesIdx);
415 } elif Length(pauliBasesSet) == 4 {
416 // for PQRS terms, create |abcd> + |a^ b^ c^ d^>
417 if pauliBasesSet[2] == 1 and pauliBasesSet[3] == 1 {
418 ApplyXorInPlace(1, pauliBasesIdx);
419 } elif pauliBasesSet[2] == 2 and pauliBasesSet[3] == 2 {
420 ApplyXorInPlace(2, pauliBasesIdx);
421 } elif pauliBasesSet[2] == 1 and pauliBasesSet[3] == 2 {
422 ApplyXorInPlace(3, pauliBasesIdx);
423 } elif pauliBasesSet[2] == 2 and pauliBasesSet[3] == 1 {
424 ApplyXorInPlace(4, pauliBasesIdx);
425 }
426 }
427}
428
429operation ToPauliBases(idx : Int, pauliBases : Qubit[]) : Unit is Adj + Ctl {
430 let pauliBasesSet = [[1, 1, 1, 1], [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1]];
431 H(pauliBases[0]);
432
433 if idx > 0 {
434 for idxSet in 1..Length(pauliBasesSet[0]) - 1 {
435 if (pauliBasesSet[idx - 1])[idxSet] == 2 {
436 X(pauliBases[idxSet]);
437 }
438
439 CNOT(pauliBases[0], pauliBases[idxSet]);
440 }
441 }
442}
443
444// This prepares the state that selects _JWSelect_;
445operation JWOptimizedBlockEncodingStatePrep(
446 targetError : Double,
447 optimizedBEGeneratorSystem : OptimizedBEGeneratorSystem,
448 qROMIdxRegister : Qubit[],
449 qROMGarbage : Qubit[],
450 signQubit : Qubit,
451 selectZControlRegisters : Qubit[],
452 optimizedBEControlRegisters : Qubit[],
453 pauliBases : Qubit[],
454 pauliBasesIdx : Qubit[],
455 indexRegisters : Qubit[][]
456) : Unit is Adj + Ctl {
457
458 let coefficients = OptimizedBEGeneratorSystemCoeff(optimizedBEGeneratorSystem);
459 let purifiedState = PurifiedMixedState(targetError, coefficients);
460 let unitaryGenerator = (
461 optimizedBEGeneratorSystem.NumTerms,
462 idx -> ToJWSelectInput(idx, optimizedBEGeneratorSystem, _, _, _, _, _)
463 );
464 let pauliBasesUnitaryGenerator = (5, idx -> (qs => ToPauliBases(idx, qs)));
465
466 purifiedState.Prepare(qROMIdxRegister, [], qROMGarbage);
467 MultiplexOperationsFromGenerator(
468 unitaryGenerator,
469 qROMIdxRegister,
470 (signQubit, selectZControlRegisters, optimizedBEControlRegisters, pauliBasesIdx, indexRegisters)
471 );
472 MultiplexOperationsFromGenerator(pauliBasesUnitaryGenerator, pauliBasesIdx, pauliBases);
473}
474
475function JWOptimizedBlockEncodingQubitManager(
476 targetError : Double,
477 nCoeffs : Int,
478 nZ : Int,
479 nMaj : Int,
480 nIdxRegQubits : Int,
481 ctrlRegister : Qubit[]
482) : (
483 (Qubit[], Qubit[], Qubit, Qubit[], Qubit[], Qubit[], Qubit[], Qubit[][]),
484 (Qubit, Qubit[], Qubit[], Qubit[], Qubit[][]),
485 Qubit[]
486) {
487
488 let requirements = PurifiedMixedStateRequirements(targetError, nCoeffs);
489 let parts = Partitioned([requirements.NumIndexQubits, requirements.NumGarbageQubits], ctrlRegister);
490 let ((qROMIdx, qROMGarbage), rest0) = ((parts[0], parts[1]), parts[2]);
491 let ((
492 signQubit,
493 selectZControlRegisters,
494 optimizedBEControlRegisters,
495 pauliBases,
496 indexRegisters,
497 tmp
498 ), rest1) = JWSelectQubitManager(nZ, nMaj, nIdxRegQubits, rest0, []);
499 let registers = Partitioned([3], rest1);
500 let pauliBasesIdx = registers[0];
501 return (
502 (qROMIdx, qROMGarbage, signQubit, selectZControlRegisters, optimizedBEControlRegisters, pauliBases, pauliBasesIdx, indexRegisters),
503 (signQubit, selectZControlRegisters, optimizedBEControlRegisters, pauliBases, indexRegisters),
504 registers[1]
505 );
506}
507
508function JWOptimizedBlockEncodingQubitCount(
509 targetError : Double,
510 nCoeffs : Int,
511 nZ : Int,
512 nMaj : Int,
513 nIdxRegQubits : Int,
514 nTarget : Int
515) : (
516 (Int, Int),
517 (Int, Int, Int, Int, Int, Int, Int, Int[], Int)
518) {
519
520 let (nSelectTotal, (a0, a1, a2, a3, a4)) = JWSelectQubitCount(nZ, nMaj, nIdxRegQubits);
521 let requirements = PurifiedMixedStateRequirements(targetError, nCoeffs);
522 let pauliBasesIdx = 3;
523 return (
524 ((nSelectTotal + requirements.NumTotalQubits) + pauliBasesIdx, nTarget),
525 (requirements.NumIndexQubits, requirements.NumGarbageQubits, a0, a1, a2, a3, pauliBasesIdx, a4, nTarget)
526 );
527}
528
529
530operation JWOptimizedBlockEncodingStatePrepWrapper(
531 targetError : Double,
532 nCoeffs : Int,
533 optimizedBEGeneratorSystem : OptimizedBEGeneratorSystem,
534 nZ : Int,
535 nMaj : Int,
536 nIdxRegQubits : Int,
537 ctrlRegister : Qubit[]
538) : Unit is Adj + Ctl {
539
540 let (statePrepRegister, _, _) = JWOptimizedBlockEncodingQubitManager(
541 targetError,
542 nCoeffs,
543 nZ,
544 nMaj,
545 nIdxRegQubits,
546 ctrlRegister
547 );
548 let statePrepOp = JWOptimizedBlockEncodingStatePrep(targetError, optimizedBEGeneratorSystem, _, _, _, _, _, _, _, _);
549 statePrepOp(statePrepRegister);
550}
551
552
553operation JWOptimizedBlockEncodingSelect(
554 targetError : Double,
555 nCoeffs : Int,
556 optimizedBEGeneratorSystem : OptimizedBEGeneratorSystem,
557 nZ : Int,
558 nMaj : Int,
559 nIdxRegQubits : Int,
560 ctrlRegister : Qubit[],
561 targetRegister : Qubit[]
562) : Unit is Adj + Ctl {
563
564 let (statePrepRegister, selectRegister, rest) = JWOptimizedBlockEncodingQubitManager(
565 targetError,
566 nCoeffs,
567 nZ,
568 nMaj,
569 nIdxRegQubits,
570 ctrlRegister
571 );
572 let selectOp = JWSelect(_, _, _, _, _, targetRegister);
573 selectOp(selectRegister);
574}
575
576
577function JWOptimizedQuantumWalkByQubitization(
578 targetError : Double,
579 data : JWOptimizedHTerms,
580 nSpinOrbitals : Int
581) : ((Int, Int), (Double, ((Qubit[], Qubit[]) => Unit is Adj + Ctl))) {
582
583 let (
584 (nCtrlRegisterQubits, nTargetRegisterQubits),
585 (oneNorm, blockEncodingReflection)
586 ) = JWOptimizedBlockEncoding(targetError, data, nSpinOrbitals);
587 return (
588 (nCtrlRegisterQubits, nTargetRegisterQubits),
589 (oneNorm, QuantumWalkByQubitization(blockEncodingReflection))
590 );
591}
592
593/// # Summary
594/// Encodes an operator of interest into a `BlockEncoding`.
595///
596/// This constructs a `BlockEncoding` unitary $U=P\cdot V\cdot P^\dagger$ that encodes some
597/// operator $H = \sum_{j}|\alpha_j|U_j$ of interest that is a linear combination of
598/// unitaries. Typically, $P$ is a state preparation unitary such that
599/// $P\ket{0}\_a=\sum_j\sqrt{\alpha_j/\|\vec\alpha\|\_2}\ket{j}\_a$,
600/// and $V=\sum_{j}\ket{j}\bra{j}\_a\otimes U_j$.
601///
602/// # Input
603/// ## statePreparation
604/// A unitary $P$ that prepares some target state.
605/// ## selector
606/// A unitary $V$ that encodes the component unitaries of $H$.
607///
608/// # Output
609/// A unitary $U$ acting jointly on registers `a` and `s` that block-
610/// encodes $H$, and satisfies $U^\dagger = U$.
611///
612/// # Remarks
613/// This `BlockEncoding` implementation gives it the properties of a
614/// `BlockEncodingReflection`.
615function BlockEncodingByLCU<'T, 'S>(
616 statePreparation : ('T => Unit is Adj + Ctl),
617 selector : (('T, 'S) => Unit is Adj + Ctl)
618) : (('T, 'S) => Unit is Adj + Ctl) {
619 return ApplyBlockEncodingByLCU(statePreparation, selector, _, _);
620}
621
622/// # Summary
623/// Implementation of `BlockEncodingByLCU`.
624operation ApplyBlockEncodingByLCU<'T, 'S>(
625 statePreparation : ('T => Unit is Adj + Ctl),
626 selector : (('T, 'S) => Unit is Adj + Ctl),
627 auxiliary : 'T,
628 system : 'S
629) : Unit is Adj + Ctl {
630 within {
631 statePreparation(auxiliary);
632 } apply {
633 selector(auxiliary, system);
634 }
635}
636
637/// # Summary
638/// Converts a block-encoding reflection into a quantum walk.
639///
640/// # Description
641/// Given a block encoding represented by a unitary $U$
642/// that encodes some operator $H$ of interest, converts it into a quantum
643/// walk $W$ containing the spectrum of $\pm e^{\pm i\sin^{-1}(H)}$.
644///
645/// # Input
646/// ## blockEncoding
647/// A unitary $U$ to be converted into a Quantum
648/// walk.
649///
650/// # Output
651/// A quantum walk $W$ acting jointly on registers `a` and `s` that block-
652/// encodes $H$, and contains the spectrum of $\pm e^{\pm i\sin^{-1}(H)}$.
653///
654/// # References
655/// - [Hamiltonian Simulation by Qubitization](https://arxiv.org/abs/1610.06546)
656/// Guang Hao Low, Isaac L. Chuang
657function QuantumWalkByQubitization(
658 blockEncoding : (Qubit[], Qubit[]) => Unit is Adj + Ctl
659) : ((Qubit[], Qubit[]) => Unit is Adj + Ctl) {
660 return ApplyQuantumWalkByQubitization(blockEncoding, _, _);
661}
662
663/// # Summary
664/// Implementation of `Qubitization`.
665operation ApplyQuantumWalkByQubitization(
666 blockEncoding : (Qubit[], Qubit[]) => Unit is Adj + Ctl,
667 auxiliary : Qubit[],
668 system : Qubit[]
669) : Unit is Adj + Ctl {
670 Exp([PauliI], -0.5 * PI(), [Head(system)]);
671 within {
672 ApplyToEachCA(X, auxiliary);
673 } apply {
674 Controlled R1(Rest(auxiliary), (PI(), Head(system)));
675 }
676 blockEncoding(auxiliary, system);
677}
678
679/// # Summary
680/// Creates a block-encoding unitary for a Hamiltonian.
681///
682/// The Hamiltonian $H=\sum_{j}\alpha_j P_j$ is described by a
683/// sum of Pauli terms $P_j$, each with real coefficient $\alpha_j$.
684///
685/// # Input
686/// ## generatorSystem
687/// A `GeneratorSystem` that describes $H$ as a sum of Pauli terms
688///
689/// # Output
690/// ## First parameter
691/// The one-norm of coefficients $\alpha=\sum_{j}|\alpha_j|$.
692/// ## Second parameter
693/// A block encoding unitary $U$ of the Hamiltonian $H$. As this unitary
694/// satisfies $U^2 = I$, it is also a reflection.
695///
696/// # Remarks
697/// This is obtained by preparing and unpreparing the state $\sum_{j}\sqrt{\alpha_j/\alpha}\ket{j}$,
698/// and constructing a multiply-controlled unitary `PrepareArbitraryStateD` and `MultiplexOperationsFromGenerator`.
699function PauliBlockEncoding(generatorSystem : GeneratorSystem) : (Double, (Qubit[], Qubit[]) => Unit is Adj + Ctl) {
700 let multiplexer = unitaryGenerator -> MultiplexOperationsFromGenerator(unitaryGenerator, _, _);
701 return PauliBlockEncodingInner(
702 generatorSystem,
703 coeff -> (qs => PreparePureStateD(coeff, Reversed(qs))),
704 multiplexer
705 );
706}
707
708/// # Summary
709/// Creates a block-encoding unitary for a Hamiltonian.
710///
711/// The Hamiltonian $H=\sum_{j}\alpha_j P_j$ is described by a
712/// sum of Pauli terms $P_j$, each with real coefficient $\alpha_j$.
713///
714/// # Input
715/// ## generatorSystem
716/// A `GeneratorSystem` that describes $H$ as a sum of Pauli terms
717/// ## statePrepUnitary
718/// A unitary operation $P$ that prepares $P\ket{0}=\sum_{j}\sqrt{\alpha_j}\ket{j}$ given
719/// an array of coefficients $\{\sqrt{\alpha}_j\}$.
720/// ## statePrepUnitary
721/// A unitary operation $V$ that applies the unitary $V_j$ controlled on index $\ket{j}$,
722/// given a function $f: j\rightarrow V_j$.
723///
724/// # Output
725/// ## First parameter
726/// The one-norm of coefficients $\alpha=\sum_{j}|\alpha_j|$.
727/// ## Second parameter
728/// A block encoding unitary $U$ of the Hamiltonian $U$. As this unitary
729/// satisfies $U^2 = I$, it is also a reflection.
730///
731/// # Remarks
732/// Example operations the prepare and unpreparing the state $\sum_{j}\sqrt{\alpha_j/\alpha}\ket{j}$,
733/// and construct a multiply-controlled unitary are
734/// `PrepareArbitraryStateD` and `MultiplexOperationsFromGenerator`.
735function PauliBlockEncodingInner(
736 generatorSystem : GeneratorSystem,
737 statePrepUnitary : (Double[] -> (Qubit[] => Unit is Adj + Ctl)),
738 multiplexer : ((Int, (Int -> (Qubit[] => Unit is Adj + Ctl))) -> ((Qubit[], Qubit[]) => Unit is Adj + Ctl))
739) : (Double, (Qubit[], Qubit[]) => Unit is Adj + Ctl) {
740 let nTerms = generatorSystem.NumEntries;
741 let op = idx -> {
742 let (_, coeff) = generatorSystem.EntryAt(idx).Term;
743 Sqrt(AbsD(coeff[0]))
744 };
745 let coefficients = MappedOverRange(op, 0..nTerms-1);
746 let oneNorm = PNorm(2.0, coefficients)^2.0;
747 let unitaryGenerator = (nTerms, idx -> PauliLCUUnitary(generatorSystem.EntryAt(idx)));
748 let statePreparation = statePrepUnitary(coefficients);
749 let selector = multiplexer(unitaryGenerator);
750 let blockEncoding = (qs0, qs1) => BlockEncodingByLCU(statePreparation, selector)(qs0, qs1);
751 return (oneNorm, blockEncoding);
752}
753
754/// # Summary
755/// Used in implementation of `PauliBlockEncoding`
756function PauliLCUUnitary(generatorIndex : GeneratorIndex) : (Qubit[] => Unit is Adj + Ctl) {
757 return ApplyPauliLCUUnitary(generatorIndex, _);
758}
759
760/// # Summary
761/// Used in implementation of `PauliBlockEncoding`
762operation ApplyPauliLCUUnitary(
763 generatorIndex : GeneratorIndex,
764 qubits : Qubit[]
765) : Unit is Adj + Ctl {
766 let (idxPaulis, coeff) = generatorIndex.Term;
767 let idxQubits = generatorIndex.Subsystem;
768 let paulis = [PauliI, PauliX, PauliY, PauliZ];
769 let pauliString = IntArrayAsPauliArray(idxPaulis);
770 let pauliQubits = Subarray(idxQubits, qubits);
771
772 ApplyPauli(pauliString, pauliQubits);
773
774 if (coeff[0] < 0.0) {
775 // -1 phase
776 Exp([PauliI], PI(), [Head(pauliQubits)]);
777 }
778}
779
780function IntArrayAsPauliArray(arr : Int[]) : Pauli[] {
781 let paulis = [PauliI, PauliX, PauliY, PauliZ];
782 mutable pauliString = [];
783 for idxP in arr {
784 pauliString += [paulis[idxP]];
785 }
786 pauliString
787}
788