We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log^0.246(1/eps)) queries, as well as a quantum algorithm that makes only O(n/sqrt(log(1/eps))) queries. We also prove a lower bound of Omega(n/log(1/eps)) in both cases; and using extremal combinatorics, prove lower bounds of Omega(log n) in the randomized case and Omega(sqrt(log n)) in the quantum case for any eps>0. We show that improving our lower bounds is intimately related to two longstanding open problems about Boolean functions: the Sensitivity Conjecture, and the relationships between query complexity and polynomial degree.
Excess quasiparticles play a crucial role in superconducting quantum devices ranging from qubits to quantum sensors. In this work we analyze their dynamics for phase-biased finite-length weak links with several Andreev subgap states, where the coupling to a microwave resonator allows for parity state (even or odd) readout. Our theory shows that almost perfect dynamical polarization in a given parity sector is achievable by applying a microwave pulse matching a transition in the opposite parity sector. Our results qualitatively explain key features of recent experiments on hybrid semiconducting nanowire Josephson junctions and provide theoretical guidelines for efficiently controlling the parity state of Andreev qubits.
We study symmetries and anomalies of dissipative Majorana chains described by Lindblad dynamics. Using the operator-state mapping, we represent the Lindbladian as a non-Hermitian operator on a doubled Hilbert space. In this formulation, the ket and bra contours admit strong fermion parities and strong translations, while their diagonal combinations define weak symmetries. For even and odd chain lengths, we diagnose anomalies by comparing symmetry algebras with and without weak fermion-parity defects. These algebras retain the lattice precursor of the modulo-
8 anomaly of the closed Majorana chain and exhibit projective relations between strong fermion parity and weak translation, as well as between weak fermion parity and strong translation, which are intrinsic to open quantum systems. We establish the IR correspondence between the lattice symmetry algebras and those of the doubled Majorana CFT in four spin sectors, identifying chiral fermion parities emanated from the lattice translations. Finally, we develop the lattice bosonization of the dissipative chain. For even length with collective energy dephasing, combining the defect and no-defect sectors and imposing GSO projections gives rise to an Ising Lindbladian with non-invertible Kramers--Wannier symmetries descending from the anomalous strong translation and fermion parity of the Majorana chain. For odd length, constructing mutually commuting ket- and bra-sector spin operators instead yields an Ising Lindbladian with a Kramers--Wannier duality defect. Our results provide a controlled framework for extending lattice anomalies and non-invertible symmetries to open quantum systems.
A possible two-qubit gate for optical quantum computing is the parity gate based on the weak Kerr effect. Two photonic qubits modulate the phase of a coherent state, and a quadrature measurement of the coherent state reveals the parity of the two qubits without destroying the photons. This can be used to create so-called cluster states, a universal resource for quantum computing. Here, the effect of self-phase modulation on the parity gate is studied, introducing generating functions for the Wigner function of a modulated coherent state. For materials with non-electromagnetically-induced-transparency-based Kerr nonlinearities, there is typically a self-phase modulation that is half the magnitude of the cross-phase modulation. Therefore, this effect cannot be ignored. It is shown that for a large class of physical implementations of the phase modulation, the quadrature measurement cannot distinguish between odd and even parity. Consequently, weak nonlinear parity gates must be implemented with physical systems where the self-phase modulation is negligible.