IBM's quantum experience offers computing up to 15 qubits however through my search of current literature the largest implementation for the algorithm has been with 4 qubits. Is there an issue, preventing people from increasing the size of the algorithm?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Welcome to the quantum computing stack exchange, Grover's algorithm is defined for an infinite number of qubits. You need $n \approx \log_2 (N)$ qubits where $N$ is the number of items searched, so the number of qubits needed depends on the number of items changed. Pay attention you need to round up.
The problem is, a physical quantum computer needs to have a property called connectivity. Connectivity is the ability for qubits to have a link and therefor be in superposition (comment if you need help with the terminology). Since all the qubits used for searching with Grover's Algorithm have to be in a superposition, you need the maximum connectivity to be able to perform the algorithm.
I am in no means an expert on the subject, but I think the higher the connectivity, the harder it is to keep the state coherent (this means making sure that no noisy errors happen). Therefor, the algorithm may not be performed on larger quantum computers (with $\approx$30 qubits), since they do not have the required connectivity.
However, I know there exist quantum computers with 15 qubits and maximum connectivity, though maybe they have other technical restrictions. I am pretty sure that Grover's Algorithm was executed on a larger number of qubits, so I would consider doing a bit more research. In any case, you can always simulate the program on your own computer like languages like Cirq, Qiskit and Q#.
If you have any other questions, please ask !
-
1$\begingroup$ Thank you so much for the excellent explanation, it really really means the world to me. I've already simulated a 2 Qubit Grover's Algorithm (the one one the qiksit documentation) on my computer, using Qiskit. I've been trying to re-create a 3 qubit algorithm from scratch, is there a way to increase/scale the number of Qbits in the algorithm without needing to create a whole new circuit everytime? $\endgroup$ Commented Feb 23, 2021 at 16:23
-
1$\begingroup$ A high-level implementation of Grover's search will take the number of qubits and the quantum oracle as parameters and scale easily (the trickiest part is the oracle implementation, not the search algorithm part). You can see examples at docs.microsoft.com/en-us/learn/modules/… or at github.com/Microsoft/QuantumKatas/#grovers-search-algorithm $\endgroup$ Commented Feb 23, 2021 at 19:45
-
1$\begingroup$ @JamesBian The power of Grover's algorithm comes from the large flexibility it has. As you assign every thing you have in your list of elements to search to a specific basis, you only need as many qubits that can create the number of basis states you need. Then you need an oracle $|U_s\rangle$ (which recognizes a correct answer to the search you are doing), this is the hard part. Finally, the magic happens with the diffusion operator, $|U_\omega \rangle$. Applying each in an altering fashion you can search for the right thing. Tell me if you want any resources to learn more. $\endgroup$ Commented Feb 23, 2021 at 20:55
-
1$\begingroup$ @JamesBian For the specific case of the qiskit tutorial, as it is designed to be accessible and easy to understand, they decided to remain very low-level (means using pretty basic functions). Qiskit of course offers more powerful "automation" with function which apply gates on every qubit. However, I am not very good as qiskit (I am a Q# user, which offers the same capabilities) but you can do it for sure, the compiler will automatically create the circuit. $\endgroup$ Commented Feb 23, 2021 at 21:04