GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
8a151f109cece83aeea78e74d62cd6f25e7996a3

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/library/fixed_point/src

library/fixed_point/src/Polynomial.qs

139lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation. All rights reserved.
2// Licensed under the MIT License.
3
4import Types.FixedPoint;
5import Init.PrepareFxP;
6import Facts.AssertFormatsAreIdenticalFxP;
7
8
9/// # Summary
10/// Evaluates a polynomial in a fixed-point representation.
11///
12/// # Input
13/// ## coefficients
14/// Coefficients of the polynomial as a double array, i.e., the array
15/// $[a_0, a_1, ..., a_d]$ for the polynomial
16/// $P(x) = a_0 + a_1 x + \cdots + a_d x^d$.
17/// ## fpx
18/// Input fixed-point number for which to evaluate the polynomial.
19/// ## result
20/// Output fixed-point number which will hold $P(x)$. Must be in state
21/// $\ket{0}$ initially.
22@Config(Unrestricted)
23operation EvaluatePolynomialFxP(coefficients : Double[], fpx : FixedPoint, result : FixedPoint) : Unit is Adj {
24 body (...) {
25 Controlled EvaluatePolynomialFxP([], (coefficients, fpx, result));
26 }
27 controlled (controls, ...) {
28 import Operations.AddConstantFxP;
29
30 Facts.AssertFormatsAreIdenticalFxP([fpx, result]);
31 let degree = Length(coefficients) - 1;
32 let p = fpx::IntegerBits;
33 let n = Length(fpx::Register);
34 if degree == 0 {
35 Controlled PrepareFxP(controls, (coefficients[0], result));
36 } elif degree > 0 {
37 // initialize ancillary register to a_d
38 use qubits = Qubit[n * degree];
39 within {
40 let firstIterate = FixedPoint(p, qubits[(degree - 1) * n..degree * n - 1]);
41 PrepareFxP(coefficients[degree], firstIterate);
42 for d in degree..(-1)..2 {
43 let currentIterate = FixedPoint(p, qubits[(d - 1) * n..d * n - 1]);
44 let nextIterate = FixedPoint(p, qubits[(d - 2) * n..(d - 1) * n - 1]);
45 // multiply by x and then add current coefficient
46 Operations.MultiplyFxP(currentIterate, fpx, nextIterate);
47 AddConstantFxP(coefficients[d-1], nextIterate);
48 }
49 } apply {
50 import Operations.MultiplyFxP;
51 let finalIterate = FixedPoint(p, qubits[0..n-1]);
52 // final multiplication into the result register
53 Controlled MultiplyFxP(controls, (finalIterate, fpx, result));
54 // add a_0 to complete polynomial evaluation and
55 Controlled AddConstantFxP(controls, (coefficients[0], result));
56 }
57 }
58 }
59}
60
61/// # Summary
62/// Evaluates an even polynomial in a fixed-point representation.
63///
64/// # Input
65/// ## coefficients
66/// Coefficients of the even polynomial as a double array, i.e., the array
67/// $[a_0, a_1, ..., a_k]$ for the even polynomial
68/// $P(x) = a_0 + a_1 x^2 + \cdots + a_k x^{2k}$.
69/// ## fpx
70/// Input fixed-point number for which to evaluate the polynomial.
71/// ## result
72/// Output fixed-point number which will hold $P(x)$. Must be in state
73/// $\ket{0}$ initially.
74@Config(Unrestricted)
75operation EvaluateEvenPolynomialFxP(coefficients : Double[], fpx : FixedPoint, result : FixedPoint) : Unit is Adj {
76 body (...) {
77 Controlled EvaluateEvenPolynomialFxP([], (coefficients, fpx, result));
78 }
79 controlled (controls, ...) {
80 import Operations.SquareFxP;
81
82 Facts.AssertFormatsAreIdenticalFxP([fpx, result]);
83 let halfDegree = Length(coefficients) - 1;
84 let n = Length(fpx::Register);
85
86 if halfDegree == 0 {
87 Controlled PrepareFxP(controls, (coefficients[0], result));
88 } elif halfDegree > 0 {
89 // initialize auxiliary register to a_d
90 use xsSquared = Qubit[n];
91 let fpxSquared = FixedPoint(fpx::IntegerBits, xsSquared);
92 within {
93 SquareFxP(fpx, fpxSquared);
94 } apply {
95 Controlled EvaluatePolynomialFxP(controls, (coefficients, fpxSquared, result));
96 }
97 }
98 }
99}
100
101/// # Summary
102/// Evaluates an odd polynomial in a fixed-point representation.
103///
104/// # Input
105/// ## coefficients
106/// Coefficients of the odd polynomial as a double array, i.e., the array
107/// $[a_0, a_1, ..., a_k]$ for the odd polynomial
108/// $P(x) = a_0 x + a_1 x^3 + \cdots + a_k x^{2k+1}$.
109/// ## fpx
110/// Input fixed-point number for which to evaluate the polynomial.
111/// ## result
112/// Output fixed-point number which will hold P(x). Must be in state
113/// $\ket{0}$ initially.
114@Config(Unrestricted)
115operation EvaluateOddPolynomialFxP(coefficients : Double[], fpx : FixedPoint, result : FixedPoint) : Unit is Adj {
116 body (...) {
117 Controlled EvaluateOddPolynomialFxP([], (coefficients, fpx, result));
118 }
119 controlled (controls, ...) {
120 import Operations.MultiplyFxP;
121 AssertFormatsAreIdenticalFxP([fpx, result]);
122 let halfDegree = Length(coefficients) - 1;
123 let n = Length(fpx::Register);
124 if halfDegree >= 0 {
125 use tmpResult = Qubit[n];
126 let tmpResultFp = FixedPoint(fpx::IntegerBits, tmpResult);
127 within {
128 EvaluateEvenPolynomialFxP(coefficients, fpx, tmpResultFp);
129 } apply {
130 Controlled MultiplyFxP(controls, (fpx, tmpResultFp, result));
131 }
132 }
133 }
134}
135
136export
137 EvaluatePolynomialFxP,
138 EvaluateEvenPolynomialFxP,
139 EvaluateOddPolynomialFxP;