Standard fermion-to-qubit encodings (Jordan–Wigner, Bravyi–Kitaev, the Bravyi–Kitaev tree, parity, ternary tree) are related by Clifford transformations, so they form a gauge group acting on the classical-simulability problem. This code demonstrates the central split: the Pauli weight and causal-cone width are gauge-covariant (re-encoding can lower them exponentially), while the dynamical-Lie-algebra dimension and the non-stabilizerness (magic) are gauge-invariant. Trainability — the cost landscape, the gradient, and the barren-plateau variance — is gauge-invariant to machine precision.
Standard fermion-to-qubit encodings (Jordan–Wigner, Bravyi–Kitaev, the Bravyi–Kitaev tree, parity, ternary tree) are related by Clifford transformations, so they form a gauge group acting on the classical-simulability problem. This code demonstrates the central split: the Pauli weight and causal-cone width are gauge-covariant (re-encoding can lower them exponentially), while the dynamical-Lie-algebra dimension and the non-stabilizerness (magic) are gauge-invariant. Trainability — the cost landscape, the gradient, and the barren-plateau variance — is gauge-invariant to machine precision.
Abstract Whether a fermionic variational quantum algorithm offers genuine advantage depends on whether its outputs resist classical computation. We show that classical simulability is encoding-dependent, not intrinsic to the circuit. Standard encodings are Clifford-related, forming a gauge group, and we classify resources by how they transform under it. Pauli weight, causal-cone width, and the entanglement setting tensor-network cost are gauge-covariant: an interacting Hamiltonian's truncated Pauli-propagation cost is linear under Jordan-Wigner but logarithmic under a tree encoding, changing the verdict at fixed ansatz. Dynamical-Lie-algebra dimension and non-stabilizerness are gauge-invariant. We prove the encoding-optimized simulation cost is bounded by the invariant resources, so encoding-robust hardness requires a large Lie algebra and large magic; covariant weight is necessary but never sufficient. These routes are sufficient certificates, not a complete characterization, so the floor is an upper bound; a full classification of representation-invariant costs remains open. We confirm both invariant routes numerically, show Lie-algebra dimension separates simulable from hard instances where weight cannot, and construct a one-parameter family where all three certificates fail at once, achieving the floor. We then establish a sharp dichotomy with trainability: because the cost landscape is encoding-invariant, gradient and barren-plateau variance are exactly gauge-invariant to machine precision. This follows from faithfulness, not Clifford-equivalence, and survives symmetry tapering, so trainability shifts only by changing what the dynamics explores, such as restricting the ansatz, never by relabeling qubits. One may re-encode a circuit to ease simulation but never to ease training. These results reframe advantage claims: an advantage that is not gauge-invariant is an artifact of the encoding.
Whether a fermionic variational quantum algorithm offers a genuine quantum advantage depends on whether its outputs are classically hard to compute. We show that for such algorithms classical simulability is not an intrinsic property of the circuit. It depends on the fermion-to-qubit encoding. Standard encodings are related by Clifford transformations, so they form a gauge group, and we classify the standard simulability resources by how they transform under it. The Pauli weight, the causal-cone width, and the entanglement that sets the cost of tensor-network contraction are gauge-covariant: a generic interacting Hamiltonian whose truncated Pauli-propagation cost grows linearly in the system size under the Jordan-Wigner encoding becomes logarithmic under a tree encoding, and we exhibit the resulting change of verdict at a fixed physical ansatz. The dynamical-Lie-algebra dimension and the non-stabilizerness are gauge-invariant. From this split we prove that the encoding-optimized simulation cost isbounded by the invariant resources, so genuine, encoding-robust hardness requires both the dynamical Lie algebra and the magic to be large; the covariant weight is necessary but never sufficient. These routes are sufficient certificates of simulability, not a complete characterization, so the floor is an upper bound and a full classification of representation-invariant cost functionals is left open. We confirm both invariant simulation routes numerically, and we show that the dynamical-Lie-algebra dimension separates simulable from hard instances where the Pauli weight cannot; we also construct an explicit one-parameter interacting family for which all three certificate routes fail at once, so the floor is achieved. We then establish a sharp dichotomy with trainability. Because the cost landscape is encoding-invariant, the gradient and the barren-plateau variance are exactly gauge-invariant, which we verify to machine precision; we show further that this invariance follows from faithfulness rather than Clifford-equivalence and is robust even to symmetry tapering, so trainability can be altered only by changing what the dynamics explores, such as restricting the ansatz, never by relabeling the qubits. One may therefore re-encode a fermionic circuit to make it easier to simulate, but never to make it easier to train. These results reframe advantage claims for fermionic ansatze: an advantage that isnot gauge-invariant is an artifact of the encoding
In order to simulate a system of fermions on a quantum computer, it is necessary to represent the fermionic states and operators on qubits. This can be accomplished in multiple ways, including the well-known Jordan-Wigner transform, as well as the parity, Bravyi-Kitaev, and ternary tree encodings. Notably, the Bravyi-Kitaev encoding can be described in terms of a classical data structure, the Fenwick tree. Here we establish a correspondence between a class of classical data structures similar to the Fenwick tree, and a class of one-to-one fermion-to-qubit transforms. We present a novel fermion-to-qubit encoding based on the recently discovered "Sierpinski tree" data structure, which matches the operator locality of the ternary tree encoding, and has the additional benefit of encoding the fermionic states as computational basis states. This is analogous to the formulation of the Bravyi-Kitaev encoding in terms of the Fenwick tree.
Representations of Spin groups and Clifford algebras derived from the structure of qubit trees are introduced in this work. For ternary trees the construction is more general and reduction to binary trees is formally defined by deletion of superfluous branches. The usual Jordan–Wigner construction also may be formally obtained in this approach by bringing the process up to trivial qubit chain (trunk). The methods can also be used for effective simulation of some quantum circuits corresponding to the binary tree structure. The modeling of more general qubit trees, as well as the relationship with the mapping used in the Bravyi–Kitaev transformation, are also briefly discussed. Quanta 2022; 11: 97–114.
While fermion-to-qubit isomorphisms are mathematically invariant under exact unitary statevector transformations, their physical implementation on noisy intermediate-scale quantum (NISQ) devices introduces severe, practical measurement bottlenecks. In this work, we systematically investigate the measurement efficiency of adaptive derivative-assembled pseudo-trotter variational quantum eigensolver (ADAPT-VQE) algorithms across three critical molecular benchmarks (LiH, BeH2, and H2O) at stretched bond lengths (2xRe) covering distinct point-group symmetries. First, we establish exact representation invariance across all target multi-reference geometries, demonstrating that operator pool gradients and statevector electronic energies remain strictly isomorphic under exact mathematical execution (E(LiH) = -7.691469 Ha, E(BeH2) = -15.110110 Ha, and E(H2O) = -74.566874 Ha). Second, we quantify the hardware measurement overhead by partitioning operator pool observables into qubit-wise commuting (QWC) tensor-product basis (TPB) cliques. We reveal that while both Jordan-Wigner (JW) and Bravyi-Kitaev (BK) encodings yield identical total Pauli term counts across the singlet excitation manifold (128 terms for H2O and BeH2), the hierarchical binary-tree layout of the BK mapping dramatically compresses the required measurement circuits---achieving up to a 45.31% reduction in total hardware execution steps compared to 12.50% under JW. Our findings demonstrate that tree-structured mappers serve as implicit, highly efficient measurement-packing engines for adaptive quantum simulations without altering the underlying variational trajectory.
We argue that all locality-preserving mappings between fermionic observables and Pauli matrices on a two-dimensional lattice can be generated from the exact bosonization in Chen et al. [Ann.Phys.(N.Y) 393, 234 (2018)], whose gauge constraints project onto the subspace of the toric code with emergent fermions.Starting from the exact bosonization and applying Clifford finite-depth generalized local unitary transformation, we can achieve all possible fermion-to-qubit mappings (up to the re-pairing of Majorana fermions).In particular, we discover a new supercompact encoding using 1.25 qubits per fermion on the square lattice.We prove the existence of finite-depth quantum circuits to obtain fermion-to-qubit mappings with qubit-fermion ratios r = 1 + 1/2k for positive integers k, utilizing the trivialness of quantum cellular automata in two spatial dimensions.Also, we provide direct constructions of fermion-to-qubit mappings with ratios arbitrarily close to 1.When the ratio reaches 1, the fermion-to-qubit mapping reduces to the one-dimensional Jordan-Wigner transformation along a certain path in the two-dimensional lattice.Finally, we explicitly demonstrate that the Bravyi-Kitaev superfast simulation, the Verstraete-Cirac auxiliary method, Kitaev's exactly solved model, the Majorana loop stabilizer codes, and the compact fermion-to-qubit mapping can all be obtained from the exact bosonization.