# Tag Info

19

Have there been any truly ground breaking algorithms besides Grover's and Shor's? It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) ...

19

There is a good explanation by Craig Gidney here (he also has other great content, including a circuit simulator, on his blog). Essentially, Grover's algorithm applies when you have a function which returns True for one of its possible inputs, and False for all the others. The job of the algorithm is to find the one that returns True. To do this we express ...

10

If you have 8 items in the list (like in your card's example), then the input of the oracle is 3 (qu)bits. Number of cards in the deck (52) is irrelevant, you need 3 bits only to encode 8 cards. You can think that 3 bits encode the position in the list of the card you are searching; then you don't know the position, but the oracle knows. So if you are ...

9

The idea for estimating the mean is roughly as follows: For any $f(x)$ that gives outputs in the reals, define a rescaled $F(x)$ that gives outputs in the range 0 to 1. We aim to estimate the mean of $F(x)$. Define a unitary $U_a$ whose operation is $$U_a:|0\rangle|0\rangle\mapsto\frac{1}{2^{n/2}}\sum_x|x\rangle(\sqrt{1-F(x)}|0\rangle+\sqrt{F(x)}|1\rangle).... 9 It sounds like you're looking for algorithms that succeed deterministically with probability 1, instead of probabilistic algorithms that succeed with probability bounded from a 1/2 by a finite amount, say 2/3. Exact is the keyword for deterministic quantum algorithms, such as in this paper Exact quantum algorithms have advantage for almost all Boolean ... 9 I've been working on this problem as well. As a beginner and a classical programmer (i.e., I don't speak Quantum Mechanics), it is difficult to get an understanding of the concepts without complete examples. I've been working with the Microsoft Q# Database Search sample. It simply searches for a specific index/key in the database, which is not very useful. ... 8 Applying the Grover iterate a total number of \lfloor \frac{\pi}{4}\sqrt{N}\rfloor times is the best choice if we want to maximize the success probability of Grover's algorithm. This is to some extent explained in Kaye, Laflamme and Mosca (KLM), but let me elaborate on the most important details here. Let n be a natural number, N = 2^n, and suppose ... 7 Apart from the ones you mentioned, another application of (a modified) Grover's algorithm which I'm aware of is solving the Collision problem in complexity theory, quantum computing and computational mathematics. It's also called the BHT algorithm. Introduction: The collision problem most often refers to the 2-to-1 version which was described by ... 7 Good question. For unstructured search, adiabatic quantum computation indeed gives the exact same \sqrt{N} speedup that the standard gate-based Grover's algorithm does, as proven in this important paper by Roland and Cerf. This agrees with the equivalence between adiabatic and gate-based quantum computation that you mentioned. (One minor correction to ... 7 Although the probability of not getting the desired result decreases exponentially, it is technically not guaranteed that one will ever get the desired measurement. Therefore, we cannot prove that Grover's algorithm is an algorithm because we cannot prove it terminates with the correct answer in a finite number of steps. (Otherwise, what part of the ... 6 Summary There is a theory of complexity of search problems (also known as relation problems). This theory includes classes called FP, FNP, and FBQP which are effectively about solving search problems with different sorts of resources. From search problems, you can also define decision problems, which allows you to relate search problems to the usual classes ... 6 Certainly! Imagine you have K=2^k copies of the search oracle U_S that you can use. Normally, you'd search by iterating the action$$ H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S, $$starting from an initial state (H|0\rangle)^{\otimes n}. This takes time \Theta(\sqrt{N}). (I'm using \mathbb{I}_n to denote the 2^n\... 6 For most functions f(x), there is nothing better than calculating all the values. After all, for most functions, there is no better way of defining the function than giving its truth table. Probably, you want to talk about the relatively small fraction of cases in which the function f(x) has some reasonably compact description. In that case, you should ... 6 You are right to recognize the complexity of building the oracle to use it with Grover's search - it is indeed the tricky part of solving the problem, and indeed a lot of sources don't consider this complexity. I like to think about the oracle as a tool to recognize the answer, not to find it. For example, if you're looking to solve a SAT problem, the ... 6 This can work. There's no reliance on powers of two or anything like that in the basic conception of the algorithm. If S is a subset of computational basis states with N elements and you have a superposition:$$\left |\phi\right> = \frac{1}{\sqrt{N}}\sum_{x \in S}\left|x\right>$$then basically all you need to do is change the classic Grover ... 6 The simplest solution is to use an ancilla in the |+\rangle state. Swap that ancilla for the oracle's output qubit, conditioned on the control qubit being false, before and after applying the oracle. Since toggling the |+\rangle state has no effect, this deactivates the oracle when the control is set. Here's this technique applied to a simple comparison ... 5 \newcommand{\bra}{\left<#1\right|}\newcommand{\ket}{\left|#1\right>}\newcommand{\braket}{\left<#1\middle|#2\right>}\newcommand{\bke}{\left<#1\middle|#2\middle|#3\right>}\newcommand{\proj}{\left|#1\right>\left<#1\right|} Since the original question was about a layman's description, I offer a slightly different solution ... 5 \newcommand{\xtarget}{\boldsymbol{x}_{\operatorname{target}}}\newcommand{\bs}{{\boldsymbol #1}}\newcommand{\on}{{\operatorname{#1}}}No, it does not. The "oracle" in Grover's algorithm is a function that, given any element \boldsymbol x_k, checks whether \boldsymbol x_k is the element we are looking for, say \xtarget. To do this, the oracle ... 5 From the perspective of defining the quantum circuit, the oracle qubit is not strictly necessary. For example, in Grover's search, you might normally define the action of the oracle as$$ U|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle, $$where f(x) returns 1 if x is the marked item. However, we always use this in a particular way, inputting (|0\... 5 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 ... 5 It doesn't have to be an inversion about the mean. Let R be the "reflect-a-vector operator", meaning$$R(v) = I - 2 |v\rangle \langle v|$$Grover's algorithm works by starting in some state |d\rangle and then alternating two reflection operations, R(s) and R(d), where s is the solution vector and d is a "diffusion vector". The choice of d ... 5 So far, it is better to say that the Grover Search algorithm, while presented as an algorithm searching through a database, would not be suited for such purpose. We prefer to say that we search through inputs of a function (the famous oracle). Loading the database/list in a quantum form would be costly in terms of qubits so for now it is not the best ... 5 There is an algorithm by Dürr and Høyer that seems to solve your problem. This algorithm finds the correct answer in \mathcal{O}(\sqrt{N}) time with probability 1/2. The crux is that they have an oracle which flips the phase of all states with a smaller value than the currently selected one. 5 (Based on the time limitation I assume we're talking about an undergraduate level project, and not something more advanced.) If you look at the questions about Grover's algorithm, you'll notice that a lot of them ask about implementing oracles for interesting tasks - or at least tasks more satisfying than looking for the state |111\rangle :-) One ... 5 In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known ... 5 The problem is with your initial assumption: the oracle for Grover's is based on a function f(value)=0/1, where 1 indicates that the value meets your search criteria and 0 indicates that it doesn't. This means that you do have to build a new oracle for each different search, but not for each different database. That said, Grover's algorithm and a quantum ... 5 The Grover diffusion operator, the second phase of the algorithm, is given by:$$D = 2\left|s\right>\left<s\right| - I$$where \left|s\right> = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\left|x\right>, which is also known as the uniform superposition, or, in the case of the question, the "original state". To see why this inverts over the mean, first ... 4 I am answering my question. After some google search, I found this image showing CCZ gate by CNOT, T dagger, and T gate. I tried this on IBM Q and it worked. I want to explore why it works but that's another story. For someone who is interested, here is my quantum circuit of Grover's algorithm finding |111> with one iteration. 4 According to this paper, A significant conclusion from this solution is that generically the generalized algorithm also has O(\sqrt{N/r}) running time Where 'r' is the number of marked states. By generalized, the authors meant a distribution with arbitrary complex amplitudes. So it seems to answer your question. That the modified initialization would ... 4 This is already partially discussed in this related question, but I'll try here to address more specifically some of the issues you rise. Generally speaking, Grover's algorithm rests upon the assumption that one is able to perform a querying operation of the form$$|i\rangle\mapsto(-1)^{f(x_i)}|i\rangle, where $i$ is the index in the database, and $x_i$ ...

Only top voted, non community-wiki answers of a minimum length are eligible