microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
katas/content/random_numbers/common.qs
118lines · modecode
| 1 | namespace Kata.Verification { |
| 2 | open Microsoft.Quantum.Arrays; |
| 3 | open Microsoft.Quantum.Diagnostics; |
| 4 | open Microsoft.Quantum.Convert; |
| 5 | open Microsoft.Quantum.Math; |
| 6 | |
| 7 | /// # Summary |
| 8 | /// Helper operation that checks that the given RNG operation generates a uniform distribution. |
| 9 | /// |
| 10 | /// # Input |
| 11 | /// ## randomGenerator |
| 12 | /// Random number generation operation to be tested. |
| 13 | /// The parameters to this operation are provided by the caller using Delay(). |
| 14 | /// ## min, max |
| 15 | /// Minimal and maximal numbers in the range to be generated, inclusive. |
| 16 | /// ## nRuns |
| 17 | /// The number of random numbers to generate for test. |
| 18 | /// |
| 19 | /// # Output |
| 20 | /// 0x0 if the generated distribution is uniform. |
| 21 | /// 0x1 if a value was generated outside the specified range. |
| 22 | /// 0x2 if the average of the distribution is outside the expected range. |
| 23 | /// 0x3 if the median of the distribution is outside the expected range. |
| 24 | /// 0x4 if the minimum count requirements were not met. |
| 25 | operation CheckUniformDistribution ( |
| 26 | randomGenerator : (Unit => Int), |
| 27 | min : Int, |
| 28 | max : Int, |
| 29 | nRuns : Int) |
| 30 | : Int { |
| 31 | let idealMean = 0.5 * IntAsDouble(max + min); |
| 32 | let rangeDividedByTwo = 0.5 * IntAsDouble(max - min); |
| 33 | // Variance = a*(a+1)/3, where a = (max-min)/2 |
| 34 | // For sample population : divide it by nRuns |
| 35 | let varianceInSamplePopulation = (rangeDividedByTwo * (rangeDividedByTwo + 1.0)) / IntAsDouble(3 * nRuns); |
| 36 | let standardDeviation = Sqrt(varianceInSamplePopulation); |
| 37 | |
| 38 | // lowRange : The lower bound of the median and average for generated dataset |
| 39 | // highRange : The upper bound of the median and average for generated dataset |
| 40 | // Set them with 3 units of std deviation for 99% accuracy. |
| 41 | let lowRange = idealMean - 3.0 * standardDeviation; |
| 42 | let highRange = idealMean + 3.0 * standardDeviation; |
| 43 | |
| 44 | let idealCopiesGenerated = IntAsDouble(nRuns) / IntAsDouble(max-min+1); |
| 45 | let minimumCopiesGenerated = (0.8 * idealCopiesGenerated > 40.0) ? 0.8 * idealCopiesGenerated | 0.0; |
| 46 | |
| 47 | mutable counts = [0, size = max + 1]; |
| 48 | mutable average = 0.0; |
| 49 | for i in 1..nRuns { |
| 50 | let val = randomGenerator(); |
| 51 | if (val < min or val > max) { |
| 52 | Message($"Unexpected number generated. Expected values from {min} to {max}, generated {val}"); |
| 53 | return 0x1; |
| 54 | } |
| 55 | set average += IntAsDouble(val); |
| 56 | set counts w/= val <- counts[val] + 1; |
| 57 | } |
| 58 | |
| 59 | set average = average / IntAsDouble(nRuns); |
| 60 | if (average < lowRange or average > highRange) { |
| 61 | Message($"Unexpected average of generated numbers. Expected between {lowRange} and {highRange}, got {average}"); |
| 62 | return 0x2; |
| 63 | } |
| 64 | |
| 65 | let median = FindMedian (counts, max+1, nRuns); |
| 66 | if (median < Floor(lowRange) or median > Ceiling(highRange)) { |
| 67 | Message($"Unexpected median of generated numbers. Expected between {Floor(lowRange)} and {Ceiling(highRange)}, got {median}."); |
| 68 | return 0x3; |
| 69 | } |
| 70 | |
| 71 | for i in min..max { |
| 72 | if counts[i] < Floor(minimumCopiesGenerated) { |
| 73 | Message($"Unexpectedly low number of {i}'s generated. Only {counts[i]} out of {nRuns} were {i}"); |
| 74 | return 0x4; |
| 75 | } |
| 76 | } |
| 77 | return 0x0; |
| 78 | } |
| 79 | |
| 80 | operation FindMedian (counts : Int[], arrSize : Int, sampleSize : Int) : Int { |
| 81 | mutable totalCount = 0; |
| 82 | for i in 0 .. arrSize - 1 { |
| 83 | set totalCount = totalCount + counts[i]; |
| 84 | if totalCount >= sampleSize / 2 { |
| 85 | return i; |
| 86 | } |
| 87 | } |
| 88 | return -1; |
| 89 | } |
| 90 | |
| 91 | operation IsSufficientlyRandom(verifier : (Unit => Int)) : Bool { |
| 92 | let results = RunRandomnessVerifier(verifier, 10); |
| 93 | Tail(results) == 0x0 |
| 94 | } |
| 95 | |
| 96 | /// # Summary |
| 97 | /// Helper operation that runs a randomness verifier up to a maximum number of times. |
| 98 | /// A single run can fail with non-negligible probability even for a "correct" random generator. |
| 99 | /// |
| 100 | /// # Input |
| 101 | /// ## verifier |
| 102 | /// Operation which verifies the a random generator. |
| 103 | /// ## maxAttempts |
| 104 | /// Maximum number of times the verifier is run until a successful result occurs. |
| 105 | /// |
| 106 | /// # Output |
| 107 | /// Array with the results of each verifier run. |
| 108 | operation RunRandomnessVerifier(verifier : (Unit => Int), maxAttempts : Int) : Int[] { |
| 109 | mutable attemptResults = []; |
| 110 | mutable result = -1; |
| 111 | repeat { |
| 112 | set result = verifier(); |
| 113 | set attemptResults += [result]; |
| 114 | } until (result == 0 or Length(attemptResults) >= maxAttempts); |
| 115 | |
| 116 | attemptResults |
| 117 | } |
| 118 | } |
| 119 | |