Efficient simulation of measurement-based uncomputation

[Strilanc]

One of the results in https://arxiv.org/abs/1902.02134 is a very efficient way to uncompute a table lookup (appendix C).

When attempting to implement this construction in Q#, I ran into a catch-22. If I want to be able to simulate big cases, I need to use the Toffoli simulator. But this construction is based on performing measurements in the X basis, and involves phase fixups, so the Toffoli simulator is not able to handle it.

I believe that these kinds of constructions are going to become more and more common, and so it would be beneficial to have a simulator capable of handling them efficiently. I don't know exactly what that would look like, but it seems like an approachable problem that a simulation framework will often need to handle.

[anpaz]

What kind of simulator do you think it's needed to support this scenario? Do you have a more concrete proposal of how you can simulate large number of qubits that support rotation without having to maintain the state of the entire space like we do in the full-state simulator?

[Strilanc]

I do have a more concrete proposal.

The user must be able to declare that they are performing an MBU (measurement based uncomputation). They need to indicate where the MBU starts, where it ends, and which qubits to measure in the X basis. Perhaps this will be done using a syntactical block, which I'll call an MBU block. Note that an MBU block implies measurements and so has no automatic adjoint or controlled variants.

The goal of an MBU block is to undo relative phasing between computational basis states caused by the X basis measurements results. When a qubit is measured in the X basis, either a + or - result occurs. In the case of a - result, a 180 degree relative phase is created between computational basis states where the qubit was ON and computational basis states where the qubit was OFF. In the case of a + result, no such relative phasing occurs.

The Toffoli simulator verifies that the phasing operations in an MBU block have corrected phasing due to randomly sampled X basis measurements on the specific state being operated on. The simulator will determine the phasing caused by the X basis measurements, tally up intermediate phasing from operations such as Z, CZ, CCZ, S, T, etc, and verify it all cancelled out. Note that this means the Toffoli simulator will allow purely phasing operations (diagonal operations), or at least it will have to within MBU blocks.

When the Toffoli simulator enters an MBU block, it does the following things:

1. Push the current state phase onto the Expected Phase Stack.
2. Choose random measurement results for the qubits being uncomputed.
3. For each measured qubit that was in the |1> state and reported a |-> result, add 180 degrees into the current state phase.

When the Toffoli simulator encounters a phasing operations within an MBU block, it does the following things:

1. Determine the amount of phasing the operation applies to the currently stored state. For example, a CS operation phases the 11 state by 90 degrees, and all other states by 0 degrees.
2. Add the determined phasing amount into the current state phase.

When the Toffoli simulator leaves an MBU block, it does the following things:

1. Pop an expected phase off of the Expected Phase Stack.
2. If the expected phase differs from the current state phase variable, the MBU block failed to correct the phasing due to the X basis measurements. Throw an error to the user complaining about this (in the same way that dropping qubits without uncomputing them causes an error).

Note that this approach does not give a universal guarantee of correctness, but it at least randomly samples individual cases and verifies that they worked correctly. There could be heuristics or test configuration related to triggering important corner cases like "all results |->" to make it possible to ensure they are covered.

def mbu(uncomputed_qubits: List, fixup: Callable):
    results = [random.randint(0, 1) for _ in uncomputed_qubits]
    negations = [simulator_state.bit(q) and r for q, r in zip(uncomputed_qubits, results)]
    prev_phase = simulator_state.phase
    if sum(negations) % 2:
        simulator_state.phase *= -1
    fixup(results)
    assert simulator_state.phase == prev_phase

[bettinaheim]

@Strilanc Writing down some notes from our conversation, I think you mentioned that if you could query the gate set of a target machine, then that would give you a decent work around here?
@swernli For your awareness.

[Strilanc]

@bettinaheim It would allow the resource estimates to be accurate, but would not allow efficient verification of more complicated measurement based uncomputations.