| Summary: | What is the computational power of a quantum computer that is restricted to transitioning from one effectively classical state to another via gates which act on only a few qudits at a time? A plausible answer is that such a machine is no more powerful than a classical computer, but this turns out to be surprisingly difficult to prove. The difficulty is that the effectively classical states referenced are concordant states, which are classical up to the choice of local classical basis, and determining the next local basis in which the state of the computer looks classical appears to be a hard problem. The recent paper by Cable and Browne (2015 New J. Phys. http://dx.doi.org/10.1088/1367-2630/17/11/113049 17 http://dx.doi.org/10.1088/1367-2630/17/11/113049 ), describes powerful new techniques for addressing this fundamental question and provides some partial answers.
|
|---|