Jacob Miller, Keith Sanders, and Akimasa Miyake have recently published a paper in Physical Review A presenting a distinctive means of demonstrating the unique computational power inherent in quantum mechanics. Their work follows other proposals in the growing topic of “quantum computational supremacy”, which aims to construct a realistic device implementing a sampling-based computational task which is otherwise impossible with any modern digital computer. Such sampling tasks must achieve a careful balance, where they are both easier to implement in a laboratory than full quantum computation, but must also be hard enough to require genuinely quantum effects to solve.
The proposal put forward by Miller, Sanders, and Miyake has several desirable features. First, it can carry out its computational task in a constant amount of time, helping to mitigate the harmful effects of experimental noise. Secondly, it is capable of seamlessly verifying the correct operation of the difficult sampling task with exactly the same resources required to perform the sampling itself. This latter property is important, since the difficulty of the sampling generally makes it extremely hard to check whether or not a realistic device is actually achieving quantum supremacy. While previous works had satisfied one or the other of these properties, the current proposal uses the framework of measurement-based quantum computation and insights from the study of quantum phases of matter to simultaneously achieve both.
(a) Quantum circuit to sample probability distributions related to certain Boolean functions. The task is expected to be intractable to modern computers. (b) Our measurement-based implementation, which realizes a sampling task and its verification procedure under the same resource requirement.