GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
swernli/parallel

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/library/rotations/src

library/rotations/src/HammingWeightPhasing.qs

102lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation. All rights reserved.
2// Licensed under the MIT License.
3
4import Std.Arrays.Enumerated, Std.Arrays.Most, Std.Arrays.Partitioned, Std.Arrays.Tail;
5import Std.Convert.IntAsDouble;
6import Std.Diagnostics.Fact;
7import Std.Math.BitSizeI, Std.Math.Floor, Std.Math.Lg, Std.Math.MaxI, Std.Math.MinI;
8
9/// # Summary
10/// Applies a Z-rotation (`Rz`) with given angle to each qubit in qs.
11///
12/// # Description
13/// This implementation is based on Hamming-weight phasing to reduce the number
14/// of rotation gates. The technique was first presented in [1], and further
15/// improved in [2] based on results in [3, 4]. Note, that the reduction of
16/// rotation gates comes at a cost of additional qubits and additional quantum
17/// operations to compute the Hamming-weight.
18///
19/// # Reference
20/// - [1](https://arxiv.org/abs/1709.06648) "Halving the cost of quantum
21/// addition", Craig Gidney.
22/// - [2](https://arxiv.org/abs/2012.09238) "Early fault-tolerant simulations of
23/// the Hubbard model", Earl T. Campbell.
24/// - [3](https://cpsc.yale.edu/sites/default/files/files/tr1260.pdf) "The exact
25/// multiplicative complexity of the Hamming weight function", Joan Boyar and
26/// René Peralta.
27/// - [4](https://arxiv.org/abs/1908.01609) "The role of multiplicative
28/// complexity in compiling low T-count oracle circuits", Giulia Meuli,
29/// Mathias Soeken, Earl Campbell, Martin Roetteler, Giovanni De Micheli.
30operation HammingWeightPhasing(angle : Double, qs : Qubit[]) : Unit {
31 WithHammingWeight(qs, (sum) => {
32 for (i, sumQubit) in Enumerated(sum) {
33 Rz(IntAsDouble(2^i) * angle, sumQubit);
34 }
35 });
36}
37
38internal operation WithHammingWeight(qs : Qubit[], action : Qubit[] => Unit) : Unit {
39 let n = Length(qs);
40
41 if n <= 1 {
42 action(qs);
43 } elif n == 2 {
44 use sum = Qubit();
45
46 within {
47 AND(qs[0], qs[1], sum);
48 CNOT(qs[0], qs[1]);
49 } apply {
50 action([qs[1], sum]);
51 }
52 } elif n == 3 {
53 WithSum(qs[0], qs[1..1], qs[2..2], action);
54 } else {
55 let splitSize = 2^(BitSizeI(n - 1) - 1);
56 let (leftLen, rightLen) = (n - splitSize, splitSize - 1);
57 // handle corner case if n is power of 2; in that case the first
58 // partition is longer than the second one, and we want to avoid that.
59 let split = Partitioned([MinI(leftLen, rightLen), MaxI(leftLen, rightLen)], qs);
60 Fact(Length(split) == 3 and Length(split[2]) == 1, $"Unexpected split for n = {n}");
61
62 WithHammingWeight(split[0], (leftHW) => {
63 WithHammingWeight(split[1], (rightHW) => {
64 WithSum(split[2][0], leftHW, rightHW, action);
65 });
66 });
67 }
68}
69
70internal operation Carry(carryIn : Qubit, x : Qubit, y : Qubit, carryOut : Qubit) : Unit is Adj {
71 CNOT(carryIn, x);
72 CNOT(carryIn, y);
73 AND(x, y, carryOut);
74 CNOT(carryIn, x);
75 CNOT(x, y);
76 CNOT(carryIn, carryOut);
77}
78
79internal operation WithSum(carry : Qubit, xs : Qubit[], ys : Qubit[], action : Qubit[] => Unit) : Unit {
80 let n = Length(ys);
81 Fact(Length(xs) <= n, "Length of xs must be less or equal to length of ys");
82 Fact(n > 0, "Length must be at least 1");
83
84 use carryOut = Qubit[n];
85 let carryIn = [carry] + Most(carryOut);
86
87 within {
88 for i in 0..n-1 {
89 if i < Length(xs) {
90 Carry(carryIn[i], xs[i], ys[i], carryOut[i]);
91 } else {
92 // there is no corresponding bit in xs; this is a version of
93 // Carry in which x == 0.
94 CNOT(carryIn[i], ys[i]);
95 AND(carryIn[i], ys[i], carryOut[i]);
96 CNOT(carryIn[i], carryOut[i]);
97 }
98 }
99 } apply {
100 action(ys + [Tail(carryOut)]);
101 }
102}