Bravyi-Kitaev binary code from Fenwick trees

[kevinsung]

Currently the implementation of the function bravyi_kitaev_code in _code_transform_functions.py uses the binary code defined via recursive matrices in arXiv:1208.5986. I think that instead, it should use the more general binary code defined via Fenwick trees in arXiv:1701.07072, to match up with our canonical implementation of the Bravyi-Kitaev transform in transforms/_bravyi_kitaev.py. I think we should keep the current function but rename it something else (haven't thought of a good name yet).

This is not a high priority but I think it would be a nice illustration of the transforms via binary codes idea, and also a fun exercise for a beginner. It should use the Fenwick tree implementation contained in transforms/_fenwick_tree.py.

[conta877]

how about recursive_bravyi_kitaev for the current version? it should be a straightforward implementation - I can work on it next weekend (unless @msteudtner wants to)

[kevinsung]

I don't think recursive_bravyi_kitaev is descriptive enough because Fenwick trees are recursive objects too.

[kevinsung]

Maybe binary_bravyi_kitaev.

[msteudtner]

Hi. I might be wrong, but I believe the Bravyi-Kitaev transform of arXiv:1208.5986 , is identical to the original proposal (https://arxiv.org/abs/quant-ph/0003137). Maybe this should somehow be taken into account in the process of picking names. I'll leave the naming to you guys though, I'm really bad at this.

[babbush]

It is true that the BK transform of arXiv:1208.598 is identical to that of arXiv:quant-ph/0003137. Technically speaking, the earlier paper was focused on simulating qubits with fermions, whereas the latter paper focused on simulating fermions with qubits. But the mapping is the same. The later paper introduced the name "Bravyi-Kitaev transform" in homage to the earlier one.

[kevinsung]

We've already picked the name bravyi_kitaev for the Fenwick tree version (as defined in transforms/_bravyi_kitaev.py). I think that picking names here should be equivalent to picking our canonical implementation, and I'd like to stick with the current implementation (but we can have a discussion about changing that). I'm not advocating removing the phrase bravyi_kitaev from the binary tree version. My opinion is that arXiv:quant-ph/0003137 introduced an idea which could be generalized in several ways, and that we should reserve simple names for commonly-used and important functions.

[msteudtner]

Would it make sense to somehow insert 'binary tree' in the name to distinguish it from the the default Bravyi-Kitaev transform, that is based on a Fenwick tree ?

[kevinsung]

@msteudtner you are totally right about arXiv:1208.5986 being the same as arXiv:quant-ph/0003137. I opened an issue at #259 to discuss changing our implementation.

[kevinsung]

Actually we should wait to resolve #259 before doing this.

[kevinsung]

Ok, #259 has been resolved by #283 and we can go ahead with this. #283 changed the implementation of bravyi_kitaev to use the original one (arXiv:quant-ph/0003137, which is equivalent to the recursive matrices one from arXiv:1208.5986), and left the old implementation from arXiv:1701.07072 in as bravyi_kitaev_tree. In my opinion, the old implementation (currently bravyi_kitaev_tree) should not be provided as a standalone function, and should only be available through the binary code transforms functionality. So that's the task.

[babbush]

I think it is good to keep the bravyi_kitaev_tree implementation. At the very least, it is helpful to people who might want to learn how that method works but don't want to need to learn how the binary code transforms work. I am going to close this issue.