GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
billti/activitybar-icon

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/samples/algorithms/HypercubeLookup/src

samples/algorithms/HypercubeLookup/src/Main.qs

126lines · modecode

RawDownload
Latest commit unavailable.
1/// # Sample
2/// Grover Search on hypercube
3
4// Import standard libraries
5import Std.Diagnostics.*;
6import Std.Arrays.*;
7import Std.Convert.*;
8import Std.Arithmetic.ApplyIfGreaterL;
9import Std.Arithmetic.IncByI;
10
11// Import table lookup algorithms
12import TableLookup.*;
13
14// Import grover search algorithm
15import GroverSearch.*;
16
17/// # Summary
18/// This sample searches for a single selected vertex of a hypercube
19/// with a distance to a query vertex below a given threshold. The distance
20/// used is a multidimensional Manhattan distance (L₁ distance).
21///
22/// # Description
23/// The sample uses Grover's search algorithm to find one of the selected
24/// vertices of a hypercube represented by a bit string of coordinates. The sample
25/// shows how to implement a quantum oracle that marks indices of vertices
26/// whose distance to the query vertex is below a given threshold. It uses table
27/// lookup library to load the vertex data and arithmetic library to compute the distance.
28///
29/// This sample demonstrates:
30/// - How to use Table Lookup and Arithmetic libraries in Q#
31/// - How to shift from a classical thinking to a quantum thinking
32/// when implementing quantum oracles. See `MarkIndexIfCloser`.
33///
34/// Things to try out:
35/// - Run Histogram to see that index 6 is the prevailing result.
36/// - Run Circuit to see the generated quantum circuit.
37/// - Change lookupAlgorithm and unlookupAlgorithm options in `GetCustomLookupOptions`
38/// to see different circuits and resource estimates. For example DoMCXLookup will
39/// trade measurements for CCZ gates.
40///
41/// Note that this sample is not intended to demonstrate a quantum advantage.
42/// Classical search would be more efficient for this particular problem.
43/// In fact, the sample includes a classical function to verify the input data.
44operation Main() : Int {
45 let tableSize = Data.TableLength();
46 let nBits = Data.TableAddressBits();
47 Message($"Using {nBits} qubits to search over {tableSize} vertices.");
48
49 let nIterations = IterationsToMarked(nBits);
50 Message($"Number of iterations needed: {nIterations}");
51
52 // Use Grover's algorithm to find one selected vertex
53 // which has a distance to the query vertex below the threshold.
54 let results = GroverSearch(
55 nBits,
56 nIterations,
57 MarkIndexIfCloser(Data.DistanceThreshold(), _)
58 );
59
60 // Return the index of the found vertex
61 BoolArrayAsInt(ResultArrayAsBoolArray(results))
62}
63
64/// # Summary
65/// Reflect if the distance from the query vertex is below the given threshold.
66///
67/// # Description
68/// This operation implements the phase oracle for Grover's algorithm.
69/// It demonstrates how to shift from a classical thinking to a quantum thinking.
70///
71/// Classically, this operation would check if the distance is below the threshold for one
72/// selected vertex at a given index. In the quantum oracle, we need to do this
73/// for many possible indices in superposition at once. Therefore, we need to use
74/// reversible unitary operations and uncompute any temporary values we create.
75operation MarkIndexIfCloser(distanceThreshold : Int, index : Qubit[]) : Unit {
76 // Allocate registers for data, distance, and phase kickback
77 use data = Qubit[Data.HypercubeDimentions()];
78 use distance = Qubit[Data.MaxDistanceBits()];
79 use phase = Qubit();
80
81 // Do the following steps in a within/apply block to ensure that all temporary
82 // values are uncomputed properly.
83 within {
84 // Prepare qubit for the phase kickback
85 X(phase);
86 H(phase);
87
88 // Classically: This would be just an indexing into a table
89 // to get one selected vertex coordinates: data = vertices[index]
90 // Quantumly: Use table lookup to load the superposition of vertex coordinates
91 // for all possible indices in superposition in the index register.
92 Lookup(GetCustomLookupOptions(), Data.HypercubeVertices(), index, data);
93
94 // Classically: This would XOR the query vertex coordinates with the selected vertex
95 // Quantumly: Use X gate on qubits where query vertex coordinates are 1
96 ApplyPauliFromBitString(PauliX, true, Data.QueryVertex(), data);
97
98 for q in data {
99 // Classically: This would increase the counter by 1 if the XORed result q is 1
100 // Quantumly: Use IncByI operation to increase the distance register.
101 // Use controlled version of it instead of measuring the q as operation needs to be reversible.
102 Controlled IncByI([q], (1, distance));
103 }
104 } apply {
105 // Classically: This would check if distance < distanceThreshold
106 // Quantumly: Use ApplyIfGreaterL to apply phase kickback if distance < distanceThreshold
107 ApplyIfGreaterL(X, IntAsBigInt(distanceThreshold), distance, phase);
108 }
109}
110
111/// # Summary
112/// Gets custom lookup options for a table lookup.
113function GetCustomLookupOptions() : LookupOptions {
114 // Note how easy it is to switch algorithms when debugging or resource estimating.
115 new LookupOptions {
116 // Play with these options to generate different circuits and resource estimates
117 lookupAlgorithm = DoSplitPPLookup(),
118 unlookupAlgorithm = DoSplitPPUnlookup(),
119 preferMeasurementBasedUncomputation = false,
120 // Our data length is 2^n so we can be strict here
121 failOnLongData = true,
122 failOnShortData = true,
123 // Relaxed option as data is aligned
124 respectExcessiveAddress = false,
125 }
126}
127