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].

The quantum Schur transform has become a foundational quantum algorithm, yet even after two decades since the seminal 2004 paper by Bacon, Chuang, and Harrow (BCH), some aspects of the transform remain insufficiently understood. Moreover, an alternative approach proposed by Krovi in 2018 was recently found to be incomplete. In this submission, we present a corrected version of Krovi's algorithm along with a detailed treatment of the high-dimensional version of the BCH Schur transform. This high-dimensional focus makes the two versions of the transform practical for regimes where the local dimension $d$ is much larger than the number of qudits $n$, with corrected Krovi's algorithm scaling as $\widetilde{O}(n^{7/2})$ in gate and depth complexity, and BCH as $\widetilde{O}(\min(n^5,nd^4))$. Krovi's version of Schur transform crucially relies on the quantum Fourier transform for the symmetric group. To that end, we revisit a quantum Fourier transform algorithm by Kawano and Sekigawa. After a careful analysis, we correct their count of elementary one- and two-qubit gates and circuit depth up from $\tilde{\mathcal{O}}(n^3)$ to $\tilde{\mathcal{O}}(n^{7/2})$. This stems from our observation that Kawano and Sekigawa's analysis treats certain complicated multi-qubit operations as elementary. We also correct a mistake in how they label the basis vectors of a certain Hilbert space, simplify their algorithm by removing an unnecessary gate, and expand significantly on the implementation details of the algorithm. Our work addresses key gaps in the literature, strengthening the algorithmic foundations of a wide range of results that rely on Schur--Weyl duality and Quantum Fourier Transform over the symmetric group in quantum information theory and quantum computation.

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.