Optimizations to reduce qubits based on non-entangled squares

[madcpf]

Reduce number of qubits used in the following cases:

• SPLIT_SLIDE and MERGE_SLIDE: if an arm of the slide/merge only has one path qubit then that qubit could be used directly as the path qubit, instead of adding a new ancilla qubit;
• CAPTURE: don't create a capture ancilla if the attacker is known to be there and there is only one path qubit.

[losos0]

Everything looks great!

[madcpf]

Everything looks great!

Thanks a lot Conrad! I tried to add back @pytest.mark.parametrize('board', BIG_CIRQ_BOARDS) in test_split_slide_merge_slide_coherence() but got the following DeviceMapping Error:
https://github.com/quantumlib/ReCirq/pull/210/checks?check_run_id=3908901393

Do you know why that happens?

Thanks!

[losos0]

I tried to add back @pytest.mark.parametrize('board', BIG_CIRQ_BOARDS) in test_split_slide_merge_slide_coherence() but got the following DeviceMapping Error: https://github.com/quantumlib/ReCirq/pull/210/checks?check_run_id=3908901393

Do you know why that happens?

It means the layout algorithm failed to find an acceptable mapping of the circuit onto the device graph. For some reason, in that case it just puts qubits that must be adjacent onto non-adjacent positions, so the error is surfaced a bit later.

[losos0]

I was trying to test how this change affects the number of moves which can be laid out on a device and found a bug where sometimes do_move forgets to return a value. I think it's coming from the (2+, 1) branch. You can check for parts without test coverage by doing python -m pip install pytest-cov and pytest --cov=. --cov-report=annotate and opening quantum_board.py,cover.

[madcpf]

ts that must be adjacent onto non-adjacent positions

I was trying to test how this change affects the number of moves which can be laid out on a device and found a bug where sometimes do_move forgets to return a value. I think it's coming from the (2+, 1) branch. You can check for parts without test coverage by doing python -m pip install pytest-cov and pytest --cov=. --cov-report=annotate and opening quantum_board.py,cover.

Thanks a lot Conrad for detecting the bug and sharing the way to show the test coverage! Bugs are fixed and test cases have been added.

[losos0]

Could you squash the changes into 1 commit? I wanted to test, but didn't manage to - the branch is apparently old enough to not work with latest Cirq, and I couldn't rebase it onto the latest code due to all the merge commits. (I suggest using git rebase origin/master instead of git merge origin/master in the future to avoid this problem.)

[losos0]

Some detritus here

[madcpf]

Thanks. It's removed.

[madcpf]

Everything looks great!

Thanks a lot Conrad!``

Could you squash the changes into 1 commit? I wanted to test, but didn't manage to - the branch is apparently old enough to not work with latest Cirq, and I couldn't rebase it onto the latest code due to all the merge commits. (I suggest using git rebase origin/master instead of git merge origin/master in the future to avoid this problem.)

Thanks Conrad. I tried to merge the past ~24 commits (which is relevant to the current effort) into one. I followed all steps in https://www.internalpointers.com/post/squash-commits-into-one-git, but it seems nothing has changed.

[losos0]

I managed to run it and on a 50-game sample, the modified code can lay out 1505/2423 moves in a 50-game sample, while the existing code gets 1447/2423. LGTM

[madcpf]

I managed to run it and on a 50-game sample, the modified code can lay out 1505/2423 moves in a 50-game sample, while the existing code gets 1447/2423. LGTM

Thanks a lot Conrad for testing it and sharing the results! I'm submitting this change now.