Complexity separations for optimal matchgate-Clifford synthesis
Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.06768
curl -X POST /api/v1/records/arxiv/2610.06768/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.06768/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'