Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Weak Parity

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Published Jan 1, 2014• 3 citations
Publisher
DOI
10.1007/978-3-662-43948-7_3

Related papers

Note on the parity operator

V. Canivell, Pere Seglar

Physics Letters A•Aug 1, 1978•2 citations

Weak Parity

Scott Aaronson, Andris Ambainis, Kaspars Balodis +1 more

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.

arXiv:1312.0036•Nov 29, 2013•0 citations

Dynamical parity selection in superconducting weak links

Nico Ackermann, Alex Zazunov, Sunghun Park +2 more

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.

arXiv:2207.05782•Physical review. B./Physical review. B•Jun 16, 2023•18 citations

Dissipative Majorana Chain---Anomalies and Non-Invertible Symmetries

Hung-Hsuan Teh, Tokiro Numasawa

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.

quant-pharXiv:2610.12607•Oct 12, 2026•1 citation

Upper Bounds and Parity Considerations

Harry A. Mavromatis

Springer eBooks•Jan 1, 1987•0 citations

Upper Bounds and Parity Considerations

Harry A. Mavromatis

Reidel texts in the mathematical sciences•Jan 1, 1992•0 citations
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-888 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.