Jamie Sikora

Oblivious transfer is a cryptographic primitive where Alice has two bits and Bob wishes to learn some function of them. Ideally, Alice should not learn Bob’s desired function choice and Bob should not learn any more than logically implied by the function value. While decent quantum protocols for this task are known, many quickly become insecure if an adversary were to control the quantum devices used in the implementation of the protocol. Here we present how some existing protocols fail in this device-independent framework, and give a fully-device independent quantum protocol for XOR oblivious transfer which is provably more secure than any classical protocol.

Quantum state discrimination is a fundamental primitive in quantum information processing, underpinning tasks in quantum communication, sensing, and learning. We study this problem through the lens of semidefinite programming and develop a general dimension-reduction framework for optimal discrimination. Our approach applies to (i) ensembles of pure states (not necessarily linearly independent), (ii) mixed states, and (iii) fully general discrimination settings in which the set of guesses and the reward assigned to each guess--state pair are arbitrary. This formulation encompasses standard minimum-error discrimination, minimum-error exclusion, discrimination with penalties for incorrect guesses, and structured reward models arising in problems such as quantum anomaly detection. We show that the resulting semidefinite program can be reduced from dimension $dL$ to $NL$, where $d$ is the Hilbert space dimension of the states, $N$ is the number of candidate states, and $L$ is the size of the set of possible guesses. Importantly, we further introduce a quantum pre-processing procedure which, given quantum access to the states to be discriminated, efficiently constructs the reduced semidefinite program, enabling our method to operate directly on quantum data. As an application, we characterize optimal identification probabilities for quantum changepoint problems in several regimes, including multiple-changepoint settings that were previously computationally inaccessible.

Quantum memory is a scarce and costly resource, yet little is known about which learning tasks remain feasible under severe memory constraints. We study the problem of computing global properties of quantum sequences when quantum systems must be measured individually, without storing or jointly processing them. In our setting, a bit string \(x \in \{0,1\}^n\) is encoded into an \(n\)-qubit product state \(\ket{\psi_{x_1}} \otimes \cdots \otimes \ket{\psi_{x_n}}\), and the goal is to infer \(f(x) \in \{0,1\}\) from measurements of this quantum encoding. We consider a simple local strategy, which we call the \emph{greedy strategy}, that applies the same optimal single-system measurement independently to each subsystem and then infers \(f(x)\) from the results. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). For general Boolean functions, we establish a universal performance guarantee, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum--Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.

The problem of quantum state classification asks how accurately one can identify an unknown quantum state that is promised to be drawn from a known set of pure states. In this work, we introduce the notion of $k$-\emph{learnability}, which captures the ability to identify the correct state using at most $k$ guesses, with zero error. We show that deciding whether a given family of states is $k$-learnable can be solved via semidefinite programming. When there are $n$ states, we present polynomial-time (in $n$) algorithms for determining $k$-learnability for two cases: when $k$ is a fixed constant or the dimension of the states is a fixed constant. When both $k$ and the dimension of the states are part of the input, we prove that there exist succinct certificates placing the problem in NP, and we establish NP-hardness by a reduction from the classical $k$-clique problem. Together, our findings delineate the boundary between efficiently solvable and intractable instances of quantum state classification in the perfect (zero-error) regime.

Modern quantum devices require high-precision Hamiltonian dynamics, but environmental noise can cause calibrated Hamiltonian parameters to drift over time, necessitating expensive recalibration. Detecting when recalibration is needed is challenging, especially since the very gates required for sophisticated verification protocols may themselves be miscalibrated. While cloud quantum computing services implement heuristic routines for triggering recalibration, the fundamental limits of optimal recalibration have yet to be illuminated. Here we study the recalibration problem by developing efficient Hamiltonian certification and \changepoint{} detection protocols in the \emph{autonomous} setting. In this setting we use only single-qubit gates and measurements and do not use any ancilla qubits, making the protocols robust to the calibration issues for multi-qubit operations they aim to detect. For an unknown $n$-qubit $M$-sparse Hamiltonian $H$, our certification protocol distinguishes whether $\|H - H_0\|_F \geq \epsilon$ or $\|H - H_0\|_F \leq O(\epsilon/\sqrt{n})$ with sample complexity $\mathcal{O}(nM^2\ln(1/\delta)/\epsilon^2)$ and total evolution time $\mathcal{O}(nM\ln(1/\delta)/\epsilon^2)$, where $H_0$ is the target Hamiltonian and $\delta$ bounds the failure probability. The protocol achieves this by evolving random stabilizer product states and performing adaptive single-qubit measurements based on a classically simulable hypothesis state. Extending this to continuous monitoring, we develop an online \changepoint{} detection algorithm using the CUSUM procedure that achieves a detection delay bound of $\mathcal{O}(nM\ln(M\falsealarm{T})/\epsilon^2)$, matching the known asymptotically optimal scaling with respect to false alarm run length $\falsealarm{T}$. Our approach enables quantum devices to autonomously monitor their own calibration status without requiring ancillary systems, entangling operations, or a trusted reference device, and provides maximum-likelihood estimates of \changepoint{} locations to identify and rerun affected computations, offering a practical solution for robust quantum computing with contemporary noisy devices.

Rabin oblivious transfer is the cryptographic task where Alice wishes to receive a bit from Bob but it may get lost with probability 1/2. In this work, we provide protocol designs which yield quantum protocols with improved security. Moreover, we provide a constant lower bound on any Rabin oblivious transfer protocol. To quantify the security of this task with asymmetric cheating notions, we introduce the notion of cheating advantage which may be of independent interest in the study of other asymmetric cryptographic primitives as well.