# Deustch algorithm using one qubit

Deutsch algorithm uses two qubits to determine the type of function. But what if we have only one qubit? How the algorithm would be implemented? And especially, how $$U_f = |x\rangle |y \oplus f(x)\rangle$$ would look like?

## 2 Answers

Unfortunately, as D.W. says, it's not possible to do Deutsch's Algorithm with only a single qubit.

The key is the line you quoted in your question: the quantum oracle for the function $$f$$ returns $$\mid x\rangle \mid y \oplus f(x)\rangle$$. This only works with two qubits.

Why can't we just make the oracle return $$\mid f(x) \rangle$$? Well, in quantum computing, all functions must be reversible (you can reconstruct the input from the output), and we have no guarantee that $$f(x)$$ is reversible. And if we force $$f(x)$$ to be reversible, then we know it's balanced, and the problem becomes trivial (return "balanced" every time).

The only way to make a reversible function out of a function that may not be reversible is to add "ancillary" or "garbage" qubits; this is how the Toffoli gate implements the non-reversible AND function. That's basically what the second qubit is doing here: without it, we can't even necessarily call the function.

You can't. If the algorithm needs two qubits, you can't implement it with just one qubit.

• I mean maybe it's possible to implement another algorithm to solve the same problem but using one qubit. – Kenenbek Arzymatov Mar 9 '19 at 22:04