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