Communications of the ACM
Computer Scientists Eliminate Pesky Quantum Computations
Nearly 30 years ago, computer scientists established that for quantum algorithms, you can wait until the end of a computation to make intermediate measurements without changing the final result.
Credit: Samuel Velasco/Quanta Magazine
As quantum computers have become more functional, our understanding of them has remained muddled. Work by a pair of computer scientists has clarified part of the picture, providing insight into what can be computed with these futuristic machines.
"It's a really nice result that has implications for quantum computation," said John Watrous of the University of Waterloo in Ontario.
The research, posted in June 2020 by Bill Fefferman and Zachary Remscrim of the University of Chicago, proves that any quantum algorithm can be rearranged to move measurements performed in the middle of the calculation to the end of the process, without changing the final result or drastically increasing the amount of memory required to carry out the task. Previously, computer scientists thought that the timing of those measurements affected memory requirements, creating a bifurcated view of the complexity of quantum algorithms.
"This has been quite annoying," said Fefferman. "We've had to talk about two complexity classes — one with intermediate measurements and one without."
From Quanta Magazine
View Full Article
No entries found