Maris Ozols

Symmetry plays a crucial role in the design and analysis of quantum protocols. This result shows a canonical circuit decomposition of a quantum comb with $G\times H$ symmetry for compact groups $G$ and $H$ using the corresponding Clebsch--Gordan transforms. By using this circuit decomposition, we propose a parametrized quantum comb with group symmetry, and derive the optimal quantum comb which transforms an unknown unitary operation $U\in \SU(d)$ to its inverse $U^\dagger$ or transpose $U^\mathsf{T}$. From numerics, we find a deterministic and exact unitary transposition protocol for $d=3$ with $7$ queries to $U$, which is improved over the protocol shown in [Y.-A. Chen et al., arXiv:2403.04704], which requires $13$ queries to $U$. We also provide the simulation of random unitaries for any compact group $G$ using the compressed oracle, which can be implemented efficiently for the unitary group. The precision of our simulation for the unitary group is improved over the path-recording oracle introduced in [F. Ma and H.-Y. Huang, arXiv:2410.10116].

Port-based teleportation (PBT) is a variant of quantum teleportation that, unlike the canonical protocol by Bennett et al., does not require a correction operation on the teleported state. Since its introduction by Ishizaka and Hiroshima in 2008, no efficient implementation of PBT was known. We close this long-standing gap by building on our recent results on representations of partially transposed permutation matrix algebras and mixed quantum Schur transform. We construct efficient quantum algorithms for probabilistic and deterministic PBT protocols on n ports of arbitrary local dimension, both for EPR and optimized resource states. We describe two constructions based on different encodings of the Gelfand-Tsetlin basis for n qudits: a standard encoding that achieves O(n) time and O(nlog(n)) space complexity, and a Yamanouchi encoding that achieves O(n^2) time and O(log(n)) space complexity, both for constant local dimension and target error. We also describe efficient circuits for preparing the optimal resource states.

Abstract Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. It can, for example, be used to amplify the correctness of a quantum device whose output is classical. However, when the output of a device is a quantum state, it is not apriori clear how to implement an analogous \emph{quantum} majority vote. To this end, we consider an extension of majority vote to quantum inputs and outputs: given a product state of the form $\ket{\phi_1, \phi_2, \dotsc ,\phi_n}$ where each qubit $\ket{\phi_i}$ is in one of two orthogonal states $\ket{\psi_0}$ or $\ket{\psi_1}$, output the majority state $\ket{\psi_0}$ or $\ket{\psi_1}$. We provide an optimal algorithm for this problem that achieves worst-case fidelity of $1/2 + \Theta(1/\sqrt{n})$. Under the promise that at least $2/3$ of the qubits are in the majority state, the fidelity increases to $1 - \Theta(1/n)$ and approaches one in the limit. More generally, we initiate the study of covariant and symmetric Boolean functions $f: \set{0,1^n} \to \set{0,1}$ with quantum inputs and outputs. We provide a simple linear program of size roughly $n/2$ for computing the optimal worst-case fidelity and show that a generalization of our algorithm is optimal for computing $f$. Our algorithm has complexity $O(n^4 \log n)$ where $n$ is the number of qubits.

Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al. (Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.