Nikolaj Bjørner

Probabilistic and Quantum Algorithms Depend on Work Outside the Algorithm

Yuri Gurevich argues that probabilistic and quantum procedures do not make algorithms themselves nondeterministic: the algorithm’s steps remain fixed, while randomness or quantum measurement comes from work performed by an external assistant, partner or oracle. His theory of assisted algorithms makes that boundary explicit by modeling both the algorithm’s state changes and its exchanges with those outside systems. Gurevich uses quantum computing as a running example, without assuming the reader knows the field.