Quantum decoherence and computational complexity - De Jesus, Brian Kenneth A. (College of Engineering, University of the Philippines Diliman, 2014)
Quantum computing has gained great interest due to its speedup over classical computing. This is not without some disadvantages, one of which we focus on is quantum decoherence. Various models of decoherence were studied and one was selected that is most suitable for computational analysis. The paper presents three findings (1) An alternative method of analysis is proposed and compared to existing analysis. (2) A demonstration of the selected method on comparison of distributed vs. non-distributed quantum algorithms. (3) A comparison of two different algorithms on the same problem. From these it is demonstrated that quantum decoherence is a significant factor in the efficiency of quantum algorithms.