Alexander May

The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results: \begin{itemize} \item We prove a $\Omega(\log \R_{0,A\rightarrow B}(f)+\log \R_{0,B\rightarrow A}(f))$ lower bound on quantum CDS where $\R_{0,A\rightarrow B}(f)$ is the classical one-way communication complexity with perfect correctness. \item We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs. \item For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of $O(\log n)$ and classical lower bound of $\Omega(n)$. \item We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed. \end{itemize} We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.

We ask how quantum correlations can be distributed among many subsystems. To address this, we define entanglement sharing schemes (ESS) where certain pairs of subsystems allow entanglement to be recovered via local operations, while other pairs must not. ESS schemes come in two variants, one where the partner system with which entanglement should be prepared is known, and one where it is not. In the case of known partners, we fully characterize the access structures realizable for ESS when using stabilizer states, and construct efficient schemes for threshold access structures, and give a conjecture for the access structures realizable with general states. In the unknown partner case, we again give a complete characterization in the stabilizer setting, additionally give a complete characterization of the case where there are no restrictions on unauthorized pairs, and we prove a set of necessary conditions on general schemes which we conjecture are also sufficient. Finally, we give an application of the theory of entanglement sharing to resolve an open problem related to the distribution of entanglement in response to time sensitive requests in quantum networks.

Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on even most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, and typically lead to non-trivial lower bounds. Concretely, we give lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\SWAP}$, the XX interaction, Haar random two qubit gates, and many others, none of which previously had known lower bounds. For the CNOT gate one of our techniques gives a tight lower bound, fully resolving its entanglement cost. Our proof technique makes use of two new properties of unitaries that we introduce, called the \emph{controllable correlation} and \emph{controllable entanglement}. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting. The lower bound from controllable correlation has an elementary proof and applies to most unitaries, but does not appear to be tight for any of the unitaries we study. The lower bound from controllable entanglement is tight for CNOT but fails for generic unitaries. Its proof is less elementary; it requires the consideration of the i.i.d. setting and application of Shannon theory results, with the characterization of finite block length Schumacher compression being a key tool.

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that $f$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships.

We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communication cost. Our first result shows that the $\Dsim$ (deterministic simultaneous message passing) cost of a Boolean function $f$ is at most the number of single-qubit magic gates in a quantum circuit computing $f$ with any quantum advice state. If we allow mid-circuit measurements and adaptive circuits, we obtain an upper bound on the two-way communication complexity of $f$ in terms of the magic + measurement cost of the circuit for $f$. As an application, we obtain magic-count lower bounds of $\Omega(n)$ for the $n$-qubit generalized Toffoli gate as well as the $n$-qubit quantum multiplexer. Our second result gives a general method to transform $\Qent$ protocols (simultaneous quantum messages with shared entanglement) into $\Rent$ protocols (simultaneous classical messages with shared entanglement) which incurs only a polynomial blowup in the communication and entanglement complexity, provided the referee's action in the $\Qent$ protocol is implementable in constant $T$-depth. The resulting $\Rent$ protocols satisfy strong privacy constraints and are $\PSM^*$ protocols (private simultaneous message passing with shared entanglement), where the referee learns almost nothing about the inputs other than the function value. As an application, we demonstrate $n$-bit partial Boolean functions whose $\Rent$ complexity is $\mathrm{polylog}(n)$ and whose $\R$ (interactive randomized) complexity is $n^{\Omega(1)}$, establishing the first exponential separations between $\Rent$ and $\R$ for Boolean functions.

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret $z$ to a referee if and only if a Boolean function $f$ has $f(x,y)=1$. Alice knows $x,z$, Bob knows $y$, and the referee knows $x,y$. Recently, a quantum analogue of this primitive called CDQS was defined and related to $f$-routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. Following the classical literature on CDS for guidance, we establish closure under negation, an amplification property, and prove a number of lower bounds on CDQS based on communication complexity.

A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, f-routing and f-BB84. These are well studied in the context of position-verification, where they are leading candidates for feasible and secure verification schemes. Both settings require an honest prover implement only O(1) quantum operations. We prove that a dishonest prover must use linear quantum resources to attack the same scheme. First, we give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Our bound can be stated in terms of the quantum non-deterministic communication complexity of f. For the equality, non-equality, and greater-than functions we obtain linear lower bounds on entanglement for f-routing and f-BB84 in the perfect setting. In a second result, which applies in the robust setting, we give a new lower bound on the number of quantum gates and measurements needed to attack these verification schemes. We lower bound the gates plus measurements linearly in the simultaneous message passing cost of the function f. This leads to a linear bound against the inner product function. This gives a clear separation between the difficulty of implementing these tasks in the honest and dishonest settings, and does so in a noise robust and loss tolerant setting.

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that $f$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships.

Determining and verifying an object's position is a fundamental task with broad practical relevance. We propose a secure quantum ranging protocol that combines quantum ranging with quantum position verification (QPV). Our method achieves Heisenberg-limited precision in position estimation while simultaneously detecting potential cheaters. Two verifiers each send out a state that is entangled in frequency space within a single optical mode. An honest prover only needs to perform simple beam-splitter operations, whereas cheaters are allowed to use arbitrary linear optical operations, one ancillary mode, and perfect quantum memories—though without access to entanglement. Our approach considers a previously unstudied security aspect to quantum ranging. It also provides a framework to quantify the precision with which a prover's position can be verified in QPV, which previously has been assumed to be infinite. We further discuss the near-term experimental implementation of our scheme and propose how a better-than-classical advantage can be observed using existing photonic technologies.

The conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in information-theoretic cryptography. Motivated by a connection to non-local quantum computation and position-based cryptography, CDS with quantum resources has recently been considered. Here, we study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in information-theoretic cryptography. We establish the following results: \begin{itemize} \item We prove a $\Omega(\log \R_{0,A\rightarrow B}(f)+\log \R_{0,B\rightarrow A}(f))$ lower bound on quantum CDS where $\R_{0,A\rightarrow B}(f)$ is the classical one-way communication complexity with perfect correctness. \item We prove a lower bound on quantum CDS in terms of two round, public coin, two-prover interactive proofs. \item For perfectly correct CDS, we give a separation for a promise version of the not-equals function, showing a quantum upper bound of $O(\log n)$ and classical lower bound of $\Omega(n)$. \item We give a logarithmic upper bound for quantum CDS on forrelation, while the best known classical algorithm is linear. We interpret this as preliminary evidence that classical and quantum CDS are separated even with correctness and security error allowed. \end{itemize} We also give a separation for classical and quantum private simultaneous message passing for a partial function, improving on an earlier relational separation. Our results use novel combinations of techniques from non-local quantum computation and communication complexity.

The conditional disclosure of secrets (CDS) primitive is among the simplest cryptographic settings in which to study the relationship between communication, randomness, and security. CDS involves two parties, Alice and Bob, who do not communicate but who wish to reveal a secret $z$ to a referee if and only if a Boolean function $f$ has $f(x,y)=1$. Alice knows $x,z$, Bob knows $y$, and the referee knows $x,y$. Recently, a quantum analogue of this primitive called CDQS was defined and related to $f$-routing, a task studied in the context of quantum position-verification. CDQS has the same inputs, outputs, and communication pattern as CDS but allows the use of shared entanglement and quantum messages. We initiate the systematic study of CDQS, with the aim of better understanding the relationship between privacy and quantum resources in the information theoretic setting. Following the classical literature on CDS for guidance, we establish closure under negation, an amplification property, and prove a number of lower bounds on CDQS based on communication complexity.

We study quantum period finding algorithms such as Simon and Shor (and its variants Ekerå-Håstad and Mosca-Ekert). For a periodic function $f$ these algorithms produce -- via some quantum embedding of $f$ -- a quantum superposition $\sum_x \ket{x}\ket{f(x)}$, which requires a certain amount of output qubits that represent $\ket{f(x)}$. We show that one can lower this amount to a single output qubit by hashing $f$ down to a single bit in an oracle setting. Namely, we replace the embedding of $f$ in quantum period finding circuits by oracle access to several embeddings of hashed versions of $f$. We show that on expectation this modification only doubles the required amount of quantum measurements, while significantly reducing the total number of qubits. For example, for Simon's period finding algorithm in some $n$-bit function $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ our hashing technique reduces the required output qubits from $n$ down to $1$, and therefore the total amount of qubits from $2n$ to $n+1$. We also show that Simon's algorithm admits real world applications with only $n+1$ qubits by giving a concrete realization of a hashed version of the cryptographic Even-Mansour construction. Our oracle-based hashed version of the Ekerå-Håstad algorithm for factoring $n$-bit RSA reduces the required qubits from $(\frac 3 2 + o(1))n$ down to $(\frac 1 2 + o(1))n$. In principle our hashing approach also works for the Mosca-Ekert algorithm, but requires strong properties of the hash function family. A hashed version of Mosca-Ekert with as few as $\mathcal{O}(\log n)$ qubits would imply classical polynomial time factoring. keywords: Quantum period finding, Simon, Even-Mansour, Shor, Ekerå -Håstad, Mosca-Ekert, minimizing qubits

Let $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ be a Boolean function with period $\vec s$. It is well-known that Simon's algorithm finds $\vec s$ in time polynomial in $n$ on quantum devices that are capable of performing error-correction. However, today's quantum devices are inherently noisy, too limited for error correction, and Simon's algorithm is not error-tolerant. We show that even noisy quantum period finding computations lead to speedups in comparison to purely classical computations. More precisely, we implemented Simon's quantum period finding circuit on the $15$-qubit quantum device IBM Q 16 Melbourne. Our experiments show that with a certain probability $\tau(n)$ we measure erroneous vectors that are not orthogonal to $\vec s$. We propose new, simple, but very effective smoothing techniques to classically mitigate physical noise effects such as e.g. IBM Q's bias towards the $0$-qubit. After smoothing, our noisy quantum device provides us a statistical distribution that we can easily transform into an LPN instance with parameters $n$ and $\tau(n)$. Hence, in the noisy case we may not hope to find periods in time polynomial in $n$. However, we still obtain quantum advantage even for large errors $\tau(n)$ close to $\frac 1 2$. Thus, period finding does not necessarily require full quantum error correction capability. keywords: Noise-tolerant Simon period finding, IBM Q 16, LPN algorithms, quantum advantage