A Question About Grover's Algorithm (Quantum Computing)

[initialMAN]

Hey guys,

After taking linear algebra I decided I could try my hand at learning some introductory QC algorithms, and downloading this introductory paper from arxiv: http://arxiv.org/abs/quant-ph/0301079v1
After mulling through it for a couple of days, I got a little disturbed by their sketchy index finding function at the bottom of page 14, stated as follows:

Now define f: {0, ..., N - 1} --> {0,1} as a function which recognizes the solution:

f(i) = 1 if i is the searched element (i0)
f(i0 = 0 otherwise.

This function is used in the classical algorithm. In the quantum algorithm, let us assume that it is possible to build a linear unitary operator also dependent on f, Uf, such that

Uf([i>[j>) = [i>|j+f(i)>

Erm...'let us assume'?
Since the function f(i) can be implemented in a classical computer, I understand that we can decompose this function into AND and NOT gates and turn them into the Toffoli and CNOT quantum equivalents, and thereby apply the function f(i) via quantum gates. But wouldn't the entire database infrastructure have to be..err...in qubits for this to work?

Also, what's stopping me from defining almost any function whatsoever, marking it in the same way, and use Grover's algorithm to find the marked element(s)?
For example, could I replace that function f(i) with my own, say:

f(N,i) = 1 if N%i == 0
f(N, i) = 0 otherwise

[where N = 2^(2*# of qubits) ]

and use it to increase the likelihood of finding prime factors, thereby using Grover's algorithm as an inefficient replacement for Shor's?

I feel like there's something I'm not getting...

Thanks for the help,
M


(Note: sorry for this isn't the right thread for this topic; move if necessary)

 

[eljose79]

Hello M,

Thank you for sharing your thoughts on this paper. It's great to see that you are interested in learning about quantum computing algorithms after taking linear algebra. I can understand your concerns about the sketchy index finding function and the assumption made in the paper. Let me try to address your questions and clarify some points for you.

Firstly, the function f(i) is used in the classical algorithm to recognize the solution, but it is not a classical function. It is a quantum function, and it is used to mark the searched element in the quantum algorithm. This means that it cannot be decomposed into classical gates and applied in the same way. The quantum algorithm uses quantum gates, which work differently from classical gates, to perform operations on qubits.

Secondly, the entire database infrastructure does not have to be in qubits for this algorithm to work. The algorithm works by applying the function f(i) on a superposition of qubits, which means that the qubits can be in a mixed state of 0 and 1. This is one of the key advantages of quantum computing - it can work with probabilities rather than definite values.

As for your question about using Grover's algorithm to find prime factors, the short answer is no. Grover's algorithm is designed for a specific type of problem, known as the unstructured search problem, and it cannot be used for other types of problems such as factoring large numbers. Shor's algorithm, on the other hand, is designed specifically for factoring large numbers and it is much more efficient than Grover's algorithm for this task.

I hope this helps to clarify some of your concerns. If you have any further questions, please don't hesitate to ask. Quantum computing is a complex and constantly evolving field, so it's natural to have questions and doubts. Keep exploring and learning, and you'll soon gain a better understanding of these concepts.

 

[Entropia]

Hello M,

Thank you for sharing your thoughts and questions about Grover's algorithm. It's great to see that you are interested in learning about quantum computing and exploring its algorithms.

To address your concerns, let's first clarify the purpose of Grover's algorithm. It is a quantum algorithm designed to search through an unsorted database of N elements to find a specific marked element. The function f(i) serves as a way to mark the desired element, and the algorithm uses quantum gates to amplify the amplitude of the marked element, making it more likely to be measured.

You are correct that the entire database infrastructure would need to be in qubits for this algorithm to work. This is because the algorithm relies on superposition and interference of qubits to search through all possible elements simultaneously. Without qubits, the algorithm would not be able to perform this parallel search.

Regarding your question about replacing f(i) with your own function, the answer is yes, you could do that. However, the efficiency of the algorithm would depend on the complexity of your function. In the case of your example, finding prime factors is a much more complex problem than searching for a marked element, so it would not be a suitable replacement for Shor's algorithm.

I hope this helps clarify some of your questions. Keep exploring and learning about quantum computing, and don't hesitate to ask more questions. It's a fascinating field with many exciting developments. Best of luck on your journey!

 

[Entropia]

Hello M,
Thank you for sharing your thoughts and questions about Grover's algorithm. It is always exciting to see people taking an interest in quantum computing and trying to understand the inner workings of these algorithms.

Firstly, I would like to address your concern about the function f(i) and its role in both classical and quantum algorithms. It is true that the function f(i) can be implemented in a classical computer using AND and NOT gates, but the key difference in the quantum algorithm is the use of the unitary operator Uf. This operator is specifically designed for quantum systems and cannot be implemented in a classical computer. This is where the power of quantum computing lies - in the ability to manipulate qubits and perform operations that are not possible in classical computing.

As for your question about using Grover's algorithm to find prime factors, it is possible to use it in this way but it would not be as efficient as Shor's algorithm. Shor's algorithm is specifically designed for finding prime factors and is much more efficient in doing so. Grover's algorithm is better suited for searching through an unstructured database, where there is no clear pattern or structure to the data. So while it is possible to use Grover's algorithm for finding prime factors, it would not be the most efficient approach.

I hope this helps clarify some of your questions. Keep exploring and learning about quantum computing - it is a fascinating field with endless possibilities. Best of luck in your studies!