Where is the parallelism in Deutsch-Jozsa algorithm?

Question

I am newbie on Quantum Computing. Actually I am a software engineer but I want to understand how quantum computers work. So my question may be absurd. Sorry about that.

I tried to understand Deutsch-Jozsa algorithm to understand how quantum computers work. I understood it mathematically. But I couldn't understand it's logic. How this algorithm finds the solution in only one iteration?

Before studying about quantum computing in depth, I have been seeing that quantum computer can perform $2^n$ ($n$ is qubits count) process same time thanks to qubits superposition in various videos on YouTube.

I have two question:

1. Where is the parallelism in Deutsch-Jozsa algorithm? As I understand, the reason why this problem can be solved in one iteration is qubits can be put any position via quantum gates on Bloch sphere. Is it true?
2. How to develop quantum algorithm? Isn't it very difficult that developing an algorithm by thinking the state of matrices?

Answer 1

In fact, in the original paper of Deutsch and Jozsa they actually implemented two oracles, here comes their procedure. If you omit the second $U_f$ and get a state $|\psi\prime>=\displaystyle\sum_{i=0}^{2N-1}(-1)^{f(i)}|i,f(i)>$, when quering the expectation value you need to put another $U_f$ on $|\phi>$ to get a state $|\phi\prime>=\displaystyle\sum_{i=0}^{2N-1}|i,f(i)>$. Otherwise, $<\phi|\psi\prime>$ always equals 0.

For your first question, the ability to using n qubits to evaluate say $2^n$ functions is parallelism. You see that for a classical computer, there are $2^n$ operations to evaluate while for the quantum computer you only need to perform the operation once (in this case if you applied n Hadamard gate beforehand). As for how the procedure works, I think what you mean is to perform a measurement and that won't work.

For the Deutsch-Jozsa, after you prepared the state $|\psi>$, what you need to do to extract the result is to get the expectation value, $<\phi|\psi>$, while if you perform a direct measurement $<\psi|\psi>$ you can not get the phase factor because there is no phase difference.

For your second question, it is difficult and all the comments I see admit this. What you need is to read some papers to find potential direction toward new algorithms.

First read this paper. Peter Shor write this paper in 2003, it includes what we have achieved and what we might to able to(although this is a rather old paper). Then there are a lot of recently hot fields like quantum machine learning, quantum network, optimization algorithms(such as using a quantum computer to solve travelling salesman problem), or some simulation algorithm for quantum systems.

Also, there are different approaches to implement quantum computing, like the quantum Turing machine, quantum annealing, quantum circuit, quantum random walk, and so on.

Answer 2

"Where is the parallelism in Deutsch-Jozsa algorithm?"

Instead of inputting just 0 or just 1 into the black box, you input both 0 and 1 into the black box at the same time, because you send $\frac{1}{\sqrt{2}}\left(|0\rangle + |1\rangle \right)$ into the black box.

As I understand, the reason why this problem can be solved in one iteration is qubits can be put any position via quantum gates on Bloch sphere. Is it true?

It's true that quantum gates can put qubits anywhere on the surface of the Bloch sphere, but the reason for the parallelism is what I said in my answer to your first question: please see above :)

"How to develop quantum algorithm? Isn't it very difficult that developing an algorithm by thinking the state of matrices?"

David Deutsch was a genius, and even he didn't come up with what we now call the Deutsch-Jozsa algorithm. He came up with an algorithm in 1985 that works only 50% of the time (and this was generalized to more than one qubit with Jozsa in the early 90s), and then it was four brilliant authors in 1998: Cleve, Eckert, Macchiavello and Mosca that came up with the version of the algorithm that you see in textbooks (and works 100% of the time, assuming no decoherence). Keep in mind that Deutsch's 1985 paper came more than a decade after Holevo discovered that n qubit can carry more information than n classical bits, and years after Feynman (the most prolific scientist in the world at the time) gave prolific talks motivating people to think about computing with hardware.

Therefore, you are correct, it's not easy to come up with something like the Deutsch-Jozsa algorithm out of thin air. Even Deutsch didn't do it, and even his version with Jozsa wasn't the modern version we see in textbooks. So how then do you program efficiently for quantum computers? Experience. Study the basic algorithms and the more you do, the more you'll get the hang of it and be able to now which quantum sub-routines to use, and how to develop your own algorithms when (and if!) you ever need to do that.