GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
be82821236a00686b004bc7fe619ad16904f7997

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms

samples/algorithms/DeutschJozsa.qs

156lines · modecode

RawDownload
Latest commit unavailable.
1/// # Sample
2/// Deutsch–Jozsa Algorithm
3///
4/// # Description
5/// Deutsch–Jozsa is a quantum algorithm that determines whether a given Boolean
6/// function 𝑓 is constant (0 on all inputs or 1 on all inputs) or balanced
7/// (1 for exactly half of the input domain and 0 for the other half).
8///
9/// This Q# program implements the Deutsch–Jozsa algorithm.
10import Std.Diagnostics.*;
11import Std.Math.*;
12import Std.Measurement.*;
13
14operation Main() : Bool[] {
15 // A Boolean function is a function that maps bitstrings to a bit:
16 // 𝑓 : {0, 1}^n → {0, 1}.
17
18 // We say that 𝑓 is constant if 𝑓(𝑥⃗) = 𝑓(𝑦⃗) for all bitstrings 𝑥⃗ and
19 // 𝑦⃗, and that 𝑓 is balanced if 𝑓 evaluates to true for exactly half of
20 // its inputs.
21
22 // If we are given a function 𝑓 as a quantum operation 𝑈 |𝑥〉|𝑦〉 =
23 // |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉, and are promised that 𝑓 is either constant or is
24 // balanced, then the Deutsch–Jozsa algorithm decides between these
25 // cases with a single application of 𝑈.
26
27 // Here, we demonstrate the use of the Deutsch-Jozsa algorithm by
28 // determining the type (constant or balanced) of various functions.
29 let functionsToTest = [
30 SimpleConstantBoolF,
31 SimpleBalancedBoolF,
32 ConstantBoolF,
33 BalancedBoolF
34 ];
35
36 mutable results = [];
37 for fn in functionsToTest {
38 let isConstant = DeutschJozsa(fn, 5);
39 results += [isConstant];
40 }
41
42 return results;
43}
44
45/// # Summary
46/// Validates the implementation of the Deutsch–Jozsa algorithm by comparing
47/// the results to the expected values.
48/// This also demonstrates how to use the `@Test` attribute to define a test operation.
49@Test()
50operation ValidateDeutschJozsa() : Unit {
51 // To see how tests verify the behavior, try changing either the algorithm or the expected values
52 // in the assertion below and observe the test failure.
53 let expectedResults = [
54 ("SimpleConstantBoolF", true),
55 ("SimpleBalancedBoolF", false),
56 ("ConstantBoolF", true),
57 ("BalancedBoolF", false)
58 ];
59 let results = Main();
60 for idx in 0..Length(expectedResults)-1 {
61 let (fnName, expected) = expectedResults[idx];
62 let actual = results[idx];
63 Fact(actual == expected, $"Function {fnName} was expected to be {(expected ? "constant" | "balanced")}, but was determined to be {(actual ? "constant" | "balanced")}.");
64 }
65}
66
67/// # Summary
68/// This operation implements the DeutschJozsa algorithm.
69/// It returns the Boolean value `true` if the function is constant and
70/// `false` if it is not.
71/// It is assumed that the function is either constant or balanced.
72///
73/// # Input
74/// ## Uf
75/// A quantum operation that implements |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉, where 𝑓 is a
76/// Boolean function, 𝑥 is an 𝑛 bit register and 𝑦 is a single qubit.
77/// ## n
78/// The number of bits in the input register |𝑥〉.
79///
80/// # Output
81/// A boolean value `true` that indicates that the function is constant and
82/// `false` that indicates that the function is balanced.
83///
84/// # See Also
85/// - For details see Section 1.4.3 of Nielsen & Chuang.
86///
87/// # References
88/// - [ *Michael A. Nielsen , Isaac L. Chuang*,
89/// Quantum Computation and Quantum Information ]
90/// (http://doi.org/10.1017/CBO9780511976667)
91operation DeutschJozsa(Uf : ((Qubit[], Qubit) => Unit), n : Int) : Bool {
92 // We allocate n + 1 clean qubits. Note that the function `Uf` is defined
93 // on inputs of the form (x, y), where x has n bits and y has 1 bit.
94 use queryRegister = Qubit[n];
95 use target = Qubit();
96
97 // The last qubit needs to be flipped so that the function will actually
98 // be computed into the phase when Uf is applied.
99 X(target);
100
101 // Now, a Hadamard transform is applied to each of the qubits.
102 H(target);
103 // We use a within-apply block to ensure that the Hadamard transform is
104 // correctly inverted on the |𝑥〉 register.
105 within {
106 for q in queryRegister {
107 H(q);
108 }
109 } apply {
110 // We apply Uf to the n+1 qubits, computing |𝑥, 𝑦〉 ↦ |𝑥, 𝑦 ⊕ 𝑓(𝑥)〉.
111 Uf(queryRegister, target);
112 }
113
114 // The following for-loop measures all qubits and resets them to the |0〉
115 // state so that they can be safely deallocated at the end of the block.
116 // The loop also sets `result` to `true` if all measurement results are
117 // `Zero`, i.e. if the function is a constant function, and sets
118 // `result` to `false` if not, which according to the assumption on 𝑓
119 // means that it must be balanced.
120 mutable result = true;
121 for q in queryRegister {
122 if MResetZ(q) == One {
123 result = false;
124 }
125 }
126
127 // Finally, the last qubit, which held the 𝑦-register, is reset.
128 Reset(target);
129 return result;
130}
131
132// Simple constant Boolean function
133operation SimpleConstantBoolF(args : Qubit[], target : Qubit) : Unit {
134 X(target);
135}
136
137// Simple balanced Boolean function
138operation SimpleBalancedBoolF(args : Qubit[], target : Qubit) : Unit {
139 CX(args[0], target);
140}
141
142// A more complex constant Boolean function.
143// It applies X to every input basis vector.
144operation ConstantBoolF(args : Qubit[], target : Qubit) : Unit {
145 for i in 0..(2^Length(args)) - 1 {
146 ApplyControlledOnInt(i, X, args, target);
147 }
148}
149
150// A more complex balanced Boolean function.
151// It applies X to half of the input basis vectors.
152operation BalancedBoolF(args : Qubit[], target : Qubit) : Unit {
153 for i in 0..2..(2^Length(args)) - 1 {
154 ApplyControlledOnInt(i, X, args, target);
155 }
156}
157