Introduction to Quantum Physics and Information Processing

116 Introduction to Quantum Physics and Information Processing

6.4 Resources and Computational Complexity

We now come to the issues that make computer scientists look to the quan-

tum paradigm for answering some of their questions on efficient algorithms.

Efficiency is quantified in terms of how the resources used for the compu-

tation scale with the number of input bits n. Typically, polynomial scaling

is termed “efficient” while exponential scaling is not. Resources are typically

time, space and energy, though the last one is less a theoretical concern than

for the physical implementation.

When analyzing the efficiency of an algorithm, it is desirable to