Repository navigation
Expand file tree
/
Copy pathOrderFinding.qs
More file actions
74 lines (64 loc) · 2.47 KB
/
Copy pathOrderFinding.qs
File metadata and controls
74 lines (64 loc) · 2.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.
namespace Microsoft.Quantum.Samples.OrderFinding {
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Math;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Synthesis;
open Microsoft.Quantum.Arithmetic;
/// # Summary
/// Given a permutation π, this function returns the
/// square of π, i.e., the permutation π².
///
/// # Input
/// ## perm
/// A permutation with elements 0, ..., n - 1
///
/// # Output
/// The square of the input permutation
///
/// # Example
/// ```Q#
/// Squared([1, 2, 3, 0]), // [2, 3, 0, 1]
/// Squared([2, 3, 0, 1]), // [0, 1, 2, 3]
/// ```
function Squared(perm : Int[]) : Int[] {
return Mapped(LookupFunction(perm), perm);
}
/// # Summary
/// Implements the Order Finding algorithm as described in L.M.K. Vandersypen et al., PRL 85, 5452, 2000 (https://arxiv.org/abs/quant-ph/0007017).
///
/// The input permutation has 2ⁿ elements. Then the quantum circuit
/// has 2n + 1 qubits, where the n + 1 upper qubits are used to create
/// a superposition over 2ⁿ⁺¹ numbers, which represent the exponents
/// of the permutation. The permutation is called n + 1 times for exponents
/// 2⁰, 2¹, ..., 2ⁿ on the lower n qubits. For each exponent, we update the
/// permutation and compute a quantum circuit using reversible logic synthesis
/// from the namespace `Microsoft.Quantum.Synthesis`.
/// Finally, a QFT is applied to the upper qubits.
///
/// # Input
/// ## perm
/// The input permutation
///
/// ## index
/// Index of permutation
///
operation FindOrder(perm : Int[], input : Int) : Int {
let n = BitSizeI(Length(perm) - 1);
mutable accumulatedPermutation = perm;
use topQubits = Qubit[n + 1];
ApplyToEach(H, topQubits);
use bottomQubits = Qubit[n];
for i in 0..n {
Controlled (ApplyPermutationUsingTransformation(accumulatedPermutation, _))([topQubits[n - i]], LittleEndian(bottomQubits));
set accumulatedPermutation = Squared(accumulatedPermutation);
}
let register = BigEndianAsLittleEndian(BigEndian(topQubits));
ApplyQuantumFourierTransform(register);
let result = MeasureInteger(register);
ResetAll(topQubits + bottomQubits);
return result;
}
}