Applied

 

So what did all that work on the Deutsch-Jzosa algorithm show.

Below, the oracle is the three CNOT gates in the middle. Without

these, the three input qubits all clock in at 0. Because of phase kickback,

they are all at 1. That is the mark of a balanced oracle function.

                                                     

                                                                          

Today, a four-input result from an actual quantum computer, many years after the stricly

theoretical algorithm. Everything that is not 1 can be attributed to noise in the system.

                                                                      

                          

                                                                *    *     *     *

I was asked about Deutsch"s original paper. From Gemini:

Quantum computing; what was the algorithm in Deutsch's initial 1985 article

You are correct to ask about Deutsch's 1985 paper, as it was a groundbreaking moment in the field of quantum computing. However, the term "algorithm" is a bit misleading in this context.

Here's why:

Deutsch's Problem: Deutsch's paper didn't actually present a specific algorithm for solving a problem. Instead, it introduced a problem designed to demonstrate the potential of quantum computers. This problem, now known as Deutsch's Problem, asks:

Given a function f(x) that takes a single bit (0 or 1) as input and outputs a single bit, is f(x) a constant function (always outputs the same value) or a balanced function (outputs 0 for one input and 1 for the other)?

Quantum Solution: Deutsch's paper showed that a quantum computer could solve this problem with a single query to the function f(x), while a classical computer would require two queries in the worst case.

No Specific Algorithm: There's no specific algorithm in the traditional sense like you'd find in classical computing. The quantum solution exploits quantum superposition and interference to achieve this efficiency. It's more accurately described as a quantum procedure or quantum protocol.

In summary: Deutsch's 1985 paper was significant for introducing a problem that could be solved more efficiently on a quantum computer. It didn't present a specific algorithm, but rather a demonstration of the potential of quantum computation.

                                                         *     *     *

Why don't we measure the output qubit. Because one term is probabilistic.