Grover's algorithm: a real life example?
Answers
Answered by
0
One main assumption to be efficient within a usage of a database is that you can load with a superposition of addresses data from a RAM, also called QRAM (see https://arxiv.org/abs/0708.1879). Then assume you have one state for the address, one state for the value, and a load operation, which loads the value of the corresponding address into the value register. So the load operation would do the step
|x⟩address|0⟩value→|x⟩address|load(x)⊕0⟩value=|x⟩address|load(x)⟩value." role="presentation" style="box-sizing: inherit; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant: inherit; font-weight: normal; font-stretch: inherit; line-height: normal; font-family: inherit; font-size: 15px; vertical-align: baseline; display: table-cell !important; text-indent: 0px; text-align: center; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; width: 10000em !important; position: relative;">|x⟩address|0⟩value→|x⟩address|load(x)⊕0⟩value=|x⟩address|load(x)⟩value.|x⟩address|0⟩value→|x⟩address|load(x)⊕0⟩value=|x⟩address|load(x)⟩value.
In the first step you apply the Hadamard gates on the address register and then apply the load operation on both registers. Then you will have a superposition of all values in the database an the value register.
Haddress⊗n|0⟩address|0⟩value=12n/2∑x=02n−1|x⟩address|0⟩value" role="presentation" style="box-sizing: inherit; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant: inherit; font-weight: normal; font-stretch: inherit; line-height: normal; font-family: inherit; font-size: 15px; vertical-align: baseline; display: table-cell !important; text-indent: 0px; text-align: center; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; width: 10000em !important; position: relative;">H⊗naddress|0⟩address|0⟩value=12n/2∑x=02n−1|x⟩address|0⟩valueHaddress⊗n|0⟩address|0⟩value=12n/2∑x=02n−1|x⟩address|0⟩value
apply load→12n/2∑x=02n−1|x⟩address|load(x)⟩value" role="presentation" style="box-sizing: inherit; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant: inherit; font-weight: normal; font-stretch: inherit; line-height: normal; font-family: inherit; font-size: 15px; vertical-align: baseline; display: table-cell !important; text-indent: 0px; text-align: center; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; width: 10000em !important; position: relative;">apply load→12n/2∑x=0
|x⟩address|0⟩value→|x⟩address|load(x)⊕0⟩value=|x⟩address|load(x)⟩value." role="presentation" style="box-sizing: inherit; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant: inherit; font-weight: normal; font-stretch: inherit; line-height: normal; font-family: inherit; font-size: 15px; vertical-align: baseline; display: table-cell !important; text-indent: 0px; text-align: center; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; width: 10000em !important; position: relative;">|x⟩address|0⟩value→|x⟩address|load(x)⊕0⟩value=|x⟩address|load(x)⟩value.|x⟩address|0⟩value→|x⟩address|load(x)⊕0⟩value=|x⟩address|load(x)⟩value.
In the first step you apply the Hadamard gates on the address register and then apply the load operation on both registers. Then you will have a superposition of all values in the database an the value register.
Haddress⊗n|0⟩address|0⟩value=12n/2∑x=02n−1|x⟩address|0⟩value" role="presentation" style="box-sizing: inherit; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant: inherit; font-weight: normal; font-stretch: inherit; line-height: normal; font-family: inherit; font-size: 15px; vertical-align: baseline; display: table-cell !important; text-indent: 0px; text-align: center; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; width: 10000em !important; position: relative;">H⊗naddress|0⟩address|0⟩value=12n/2∑x=02n−1|x⟩address|0⟩valueHaddress⊗n|0⟩address|0⟩value=12n/2∑x=02n−1|x⟩address|0⟩value
apply load→12n/2∑x=02n−1|x⟩address|load(x)⟩value" role="presentation" style="box-sizing: inherit; margin: 0px; padding: 0px; border: 0px; font-style: normal; font-variant: inherit; font-weight: normal; font-stretch: inherit; line-height: normal; font-family: inherit; font-size: 15px; vertical-align: baseline; display: table-cell !important; text-indent: 0px; text-align: center; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; width: 10000em !important; position: relative;">apply load→12n/2∑x=0
Similar questions