home | literature reviews

"Trading classical and quantum computational resources", Sergey Bravyi, Graeme Smith, John Smolin, 2016

Reviewed August 25, 2023

Citation: Bravyi, Sergey, Graeme Smith, and John A. Smolin. "Trading classical and quantum computational resources." Physical Review X 6.2 (2016): 021043.

Web: https://arxiv.org/abs/1506.01396

Tags: Universal-scheme

The main topic of this paper is the simulation of a slightly-bigger quantum computer on the quantum computer you are given, using classical resources. Namely, given an n qubit quantum computer you can simulate an n+k qubit quantum computer using a polynomial amount of extra classical and quantum resources for k=O(1).

One reason I am interested in this paper is because it is a good account of Pauli-based computation. This is a very strange scheme which works as follows. First, you initialize n qubits in a tensor product of a whole bunch of magic T-states. Then, you allow yourself to measure using Pauli matrices, and adaptively choose what measurement to make next based on the result of your previous measurements. Even more strangely, the measurements you are allowed to make are non-destructive, in the sense that they do not collapse your state. It is shown that this form of computation is equivalent to BQP.

This is interesting to contrast with destructive Pauli measurements an |0>-initialized ancillas, which only gives you the Clifford group.

This is not the same thing as measurement based quantum computation, pioneered in the paper

> Raussendorf, Robert, and Hans J. Briegel. "A one-way quantum computer." Physical review letters 86.22 (2001): 5188.

Namely, in measurement based quantum computation you also initialize with a highly-entangled state but instead of performing big simple measurements you perform small (1-qubit) complicated measurements. Additionally, the destructive nature of the measurements is used as a key part of the scheme.