microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
samples/algorithms/BernsteinVazirani.qs
160lines · modecode
| 1 | /// # Sample |
| 2 | /// Bernstein-Vazirani Algorithm |
| 3 | /// |
| 4 | /// # Description |
| 5 | /// The Bernstein-Vazirani algorithm determines the value of a bit string |
| 6 | /// encoded in a function. |
| 7 | /// |
| 8 | /// This Q# program implements the Bernstein-Vazirani algorithm. |
| 9 | import Std.Arrays.*; |
| 10 | import Std.Convert.*; |
| 11 | import Std.Diagnostics.*; |
| 12 | import Std.Math.*; |
| 13 | import Std.Measurement.*; |
| 14 | |
| 15 | operation Main() : Int[] { |
| 16 | // Consider a function 𝑓(𝑥⃗) on bitstrings 𝑥⃗ = (𝑥₀, …, 𝑥ₙ₋₁) of the form |
| 17 | // 𝑓(𝑥⃗) ≔ Σᵢ 𝑥ᵢ 𝑟ᵢ |
| 18 | // where 𝑟⃗ = (𝑟₀, …, 𝑟ₙ₋₁) is an unknown bitstring that determines the |
| 19 | // parity of 𝑓. |
| 20 | |
| 21 | // The Bernstein–Vazirani algorithm allows determining 𝑟 given a |
| 22 | // quantum operation that implements |
| 23 | // |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉. |
| 24 | |
| 25 | // The entry point function of this program, `Main`, shows how to use |
| 26 | // the `BernsteinVazirani` operation to determine the value of various |
| 27 | // integers whose bits describe 𝑟. |
| 28 | let nQubits = 10; |
| 29 | |
| 30 | // Use the Bernstein–Vazirani algorithm to determine the bit strings |
| 31 | // that various integers represent. |
| 32 | let integers = [127, 238, 512]; |
| 33 | mutable decodedIntegers = []; |
| 34 | for integer in integers { |
| 35 | // Create an operation that encodes a bit string represented by an |
| 36 | // integer as a parity operation. |
| 37 | let parityOperation = EncodeIntegerAsParityOperation(integer); |
| 38 | |
| 39 | // Use the parity operation as input to the Bernstein-Vazirani |
| 40 | // algorithm to determine the bit string. |
| 41 | let decodedBitString = BernsteinVazirani(parityOperation, nQubits); |
| 42 | let decodedInteger = ResultArrayAsInt(decodedBitString); |
| 43 | Fact( |
| 44 | decodedInteger == integer, |
| 45 | $"Decoded integer {decodedInteger}, but expected {integer}." |
| 46 | ); |
| 47 | |
| 48 | Message($"Successfully decoded bit string as int: {decodedInteger}"); |
| 49 | set decodedIntegers += [decodedInteger]; |
| 50 | } |
| 51 | |
| 52 | return decodedIntegers; |
| 53 | } |
| 54 | |
| 55 | /// # Summary |
| 56 | /// This operation implements the Bernstein-Vazirani quantum algorithm. |
| 57 | /// This algorithm computes for a given Boolean function that is promised to |
| 58 | /// be a parity 𝑓(𝑥₀, …, 𝑥ₙ₋₁) = Σᵢ 𝑟ᵢ 𝑥ᵢ a result in the form of a bit |
| 59 | /// vector (𝑟₀, …, 𝑟ₙ₋₁) corresponding to the parity function. |
| 60 | /// Note that it is promised that the function is actually a parity |
| 61 | /// function. |
| 62 | /// |
| 63 | /// # Input |
| 64 | /// ## Uf |
| 65 | /// A quantum operation that implements |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉, |
| 66 | /// where 𝑓 is a Boolean function that implements a parity Σᵢ 𝑟ᵢ 𝑥ᵢ. |
| 67 | /// ## n |
| 68 | /// The number of bits in the input register |𝑥〉. |
| 69 | /// |
| 70 | /// # Output |
| 71 | /// An array of type `Result[]` that contains the parity 𝑟⃗ = (𝑟₀, …, 𝑟ₙ₋₁). |
| 72 | /// |
| 73 | /// # See Also |
| 74 | /// - For details see Section 1.4.3 of Nielsen & Chuang. |
| 75 | /// |
| 76 | /// # References |
| 77 | /// - [ *Ethan Bernstein and Umesh Vazirani*, |
| 78 | /// SIAM J. Comput., 26(5), 1411–1473, 1997 ] |
| 79 | /// (https://doi.org/10.1137/S0097539796300921) |
| 80 | operation BernsteinVazirani(Uf : ((Qubit[], Qubit) => Unit), n : Int) : Result[] { |
| 81 | // We allocate n + 1 clean qubits. Note that the function Uf is defined |
| 82 | // on inputs of the form (x, y), where x has n bits and y has 1 bit. |
| 83 | use queryRegister = Qubit[n]; |
| 84 | use target = Qubit(); |
| 85 | |
| 86 | // The last qubit needs to be flipped so that the function will actually |
| 87 | // be computed into the phase when Uf is applied. |
| 88 | X(target); |
| 89 | |
| 90 | within { |
| 91 | // Now, a Hadamard transform is applied to each of the qubits. As |
| 92 | // the last step before the measurement, a Hadamard transform is |
| 93 | // applied to all qubits except last one. We could apply the |
| 94 | // transform to the last qubit also, but this would not affect the |
| 95 | // final outcome. |
| 96 | // We use a within-apply block to ensure that the Hadamard transform |
| 97 | // is correctly inverted. |
| 98 | ApplyToEachA(H, queryRegister); |
| 99 | } apply { |
| 100 | H(target); |
| 101 | // We now apply Uf to the n+1 qubits, computing |
| 102 | // |x, y〉 ↦ |x, y ⊕ f(x)〉. |
| 103 | Uf(queryRegister, target); |
| 104 | } |
| 105 | |
| 106 | // Measure all qubits and reset them to the |0〉 state so that they can |
| 107 | // be safely deallocated at the end of the block. |
| 108 | let resultArray = MResetEachZ(queryRegister); |
| 109 | |
| 110 | // Finally, the last qubit, which held the y-register, is reset. |
| 111 | Reset(target); |
| 112 | |
| 113 | // The result is already contained in resultArray so no further |
| 114 | // post-processing is necessary. |
| 115 | return resultArray; |
| 116 | } |
| 117 | |
| 118 | /// # Summary |
| 119 | /// Given an integer that can be represented as a bit string |
| 120 | /// 𝑟⃗ = (r₀, …, rₙ₋₁), this operation applies a unitary 𝑈 that acts on 𝑛 + 1 |
| 121 | /// qubits as: |
| 122 | /// 𝑈 |𝑥〉|𝑦〉 = |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉 |
| 123 | /// where 𝑓(𝑥) = Σᵢ 𝑥ᵢ 𝑟ᵢ mod 2. |
| 124 | /// |
| 125 | /// # Input |
| 126 | /// ## bitStringAsInt |
| 127 | /// An integer that can be represented as a bit string 𝑟⃗ used to define the |
| 128 | /// function 𝑓. |
| 129 | /// ## xRegister |
| 130 | /// Represents the |𝑥〉 register that 𝑈 acts on. |
| 131 | /// ## yQubit |
| 132 | /// Represents the |𝑦〉 qubit that 𝑈 acts on. |
| 133 | operation ApplyParityOperation( |
| 134 | bitStringAsInt : Int, |
| 135 | xRegister : Qubit[], |
| 136 | yQubit : Qubit |
| 137 | ) : Unit { |
| 138 | // `xRegister` muts have enough qubits to represent the integer. |
| 139 | let requiredBits = BitSizeI(bitStringAsInt); |
| 140 | let availableQubits = Length(xRegister); |
| 141 | Fact( |
| 142 | availableQubits >= requiredBits, |
| 143 | $"Integer value {bitStringAsInt} requires {requiredBits} bits to be represented but the quantum register only has {availableQubits} qubits" |
| 144 | ); |
| 145 | |
| 146 | // Apply the quantum operations that encode the bit string. |
| 147 | for index in IndexRange(xRegister) { |
| 148 | if ((bitStringAsInt &&& 2^index) != 0) { |
| 149 | CNOT(xRegister[index], yQubit); |
| 150 | } |
| 151 | } |
| 152 | } |
| 153 | |
| 154 | /// # Summary |
| 155 | /// Returns black-box operations (Qubit[], Qubit) => () of the form |
| 156 | /// U_f |𝑥〉|𝑦〉 = |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉. |
| 157 | /// We define 𝑓 by providing the bit string 𝑟⃗ as an integer. |
| 158 | function EncodeIntegerAsParityOperation(bitStringAsInt : Int) : (Qubit[], Qubit) => Unit { |
| 159 | return ApplyParityOperation(bitStringAsInt, _, _); |
| 160 | } |
| 161 | |