Uma Girish

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.

Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between BQP and BPP. We build on a powerful technique to differentiate quantum and classical algorithms called the level-$\ell$ Fourier growth (the sum of absolute values of Fourier coefficients of sets of size $\ell$) and show that it can also be used to differentiate quantum algorithms based on the types of resources used. We show that noise acting on a quantum algorithm dampens its Fourier growth in ways intricately linked to the type of noise. Concretely, we study noisy models of quantum computation where highly mixed states are prevalent, namely: DQC_k algorithms, where k qubits are clean and the rest are maximally mixed, and 1/2-BQP algorithms, where the initial state is maximally mixed, but the algorithm is given knowledge of the initial state at the end of the computation. We establish upper bounds on the Fourier growth of DQC_k, 1/2-BQP and BQP algorithms and leverage the differences between these bounds to derive oracle separations between these models. In particular, we show that the 2-Forrelation and 3-Forrelation problems require $N^{\Omega(1)}$ queries in the DQC_1 and 1/2-BQP models respectively. Our results are proved using a new matrix decomposition lemma that might be of independent interest.

The Forrelation problem began as a landmark example of quantum advantage, revealing dramatic separations between quantum and classical capabilities. It has since become a versatile lens for understanding both the power and limitations of quantum computation. This talk traces the evolution of Forrelation and describes how it has illuminated fundamental questions in quantum complexity, cryptography, and communication: Where does quantum computation lie within classical complexity? Can quantum cryptography be based on genuinely quantum assumptions? What is the landscape of quantum computation below BQP? How powerful is entanglement in communication? Together, these developments show how Forrelation has become a recurring guide to understanding the scope and limitations of quantum advantage.

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.

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(log N) in this model, however, every interactive randomized protocol has cost Ømega(sqrtN), settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least Ømega(log N) clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost O(log N). We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq \mathrm{poly}(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space $O(S + \log T)$ that takes as an input the description of a quantum algorithm with quantum space $S$ and time $T$, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.

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.