Quantum Computers

Unit 1 • Chapter 3

Quantum Algorithms

Summary

We have a black box function f that takes in a bit (0 or 1) and returns a bit. We aim to determine if the function is constant (always outputs the same bit) or balanced (outputs 0 and 1 equally). We can do this by comparing f(0) to f(1). Classical computers require two function calls to make this determination, while quantum computers using Deutsch's algorithm can do it in one call. Quantum functions must be reversible, meaning each output uniquely identifies the input. Techniques exist to make non-reversible gates reversible in quantum computing.

Concept Check

What type of functions return zero half the time and one half the time?

How many calls does Deutsche's algorithm need to determine if a function is constant or balanced?