More Like this

1. On the Computational Hardness of Quantum One-Wayness

   https://doi.org/10.22331/q-2025-03-27-1679  

   Cavalar, Bruno; Goldin, Eli; Gray, Matthew; Hall, Peter; Liu, Yanyi; Pelecanos, Angelos (March 2025, Quantum)

   There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing $n$bits to $\log n+1$qubits can be used to build one-way state generators and pseudorandom states compressing $n$bits to $\omega (\log n)$qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than $c\log n$-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a $\mathrm{P}\mathrm{P}$oracle.An interesting implication of our results is that a $t\left(n\right)$-copy one-way state generator exists unconditionally, for every $t\left(n\right)=o(n/\log n)$. This contrasts nicely with the previously known fact that $O\left(n\right)$-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments. 

   more » « less
2. A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games

   https://doi.org/10.22331/q-2025-05-06-1737  

   Vasconcelos, Francisca; Vlatakis-Gkaragkounis, Emmanouil-Vasileios; Mertikopoulos, Panayotis; Piliouras, Georgios; Jordan, Michael I (May 2025, Quantum)

   Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, specifically, quantum zero-sum games. Central to classical game theory is the efficient algorithmic computation of Nash equilibria, which represent optimal strategies for both players. In 2008, Jain and Watrous proposed the first classical algorithm for computing equilibria in quantum zero-sum games using the Matrix Multiplicative Weight Updates (MMWU) method to achieve a convergence rate of $\mathcal{O}\left(d/{ϵ}^2\right)$iterations to $ϵ$-Nash equilibria in the $4^d$-dimensional spectraplex. In this work, we propose a hierarchy of quantum optimization algorithms that generalize MMWU via an extra-gradient mechanism. Notably, within this proposed hierarchy, we introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $\mathcal{O}\left(d/ϵ\right)$iterations to $ϵ$-Nash equilibria. This quadratic speed-up relative to Jain and Watrous' original algorithm sets a new benchmark for computing $ϵ$-Nash equilibria in quantum zero-sum games. 

   more » « less
3. Bell state analyzer for spectrally distinct photons

   https://doi.org/10.1364/OPTICA.443302  

   Lingaraju, Navin_B; Lu, Hsuan-Hao; Leaird, Daniel_E; Estrella, Steven; Lukens, Joseph_M; Weiner, Andrew_M (March 2022, Optica)

   We demonstrate a Bell state analyzer that operates directly on frequency mismatch. Based on electro-optic modulators and Fourier-transform pulse shapers, our quantum frequency processor design implements interleaved Hadamard gates in discrete frequency modes. Experimental tests on entangled-photon inputs reveal fidelities of $\sim <\#comment/>98\mathrm{\%<\#comment/>}$for discriminating between the $|{\mathrm{\Psi <\#comment/>}}^{+}⟩<\#comment/>$and $|{\mathrm{\Psi <\#comment/>}}^{-<\#comment/>}⟩<\#comment/>$frequency-bin Bell states. Our approach resolves the tension between wavelength-multiplexed state transport and high-fidelity Bell state measurements, which typically require spectral indistinguishability. 

   more » « less
4. A single-point Reshetnyak’s theorem

   https://doi.org/10.1090/tran/9415  

   Kangasniemi, Ilmari; Onninen, Jani (May 2025, Transactions of the American Mathematical Society)

   We prove a single-value version of Reshetnyak’s theorem. Namely, if a non-constant map $f\in W_{\mathrm{l}\mathrm{o}\mathrm{c}}^{1,n}(\mathrm{\Omega },{\mathbb{R}}^n)$ from a domain $\mathrm{\Omega }\subset {\mathbb{R}}^n$ satisfies the estimate $\left|Df\right(x){|}^n\le K{J}_f(x)+\mathrm{\Sigma }(x\left)\right|f\left(x\right)-y_0{|}^n$ at almost every $x\in \mathrm{\Omega }$ for some $K\ge 1$, $y_0\in {\mathbb{R}}^n$ and $\mathrm{\Sigma }\in L_{\mathrm{l}\mathrm{o}\mathrm{c}}^{1+\epsilon }\left(\mathrm{\Omega }\right)$, then $f^{-1}\left\{y_0\right\}$ is discrete, the local index $i(x,f)$ is positive in $f^{-1}\left\{y_0\right\}$, and every neighborhood of a point of $f^{-1}\left\{y_0\right\}$ is mapped to a neighborhood of $y_0$. Assuming this estimate for a fixed $K$ at every $y_0\in {\mathbb{R}}^n$ is equivalent to assuming that the map $f$ is $K$-quasiregular, even if the choice of $\mathrm{\Sigma }$ is different for each $y_0$. Since the estimate also yields a single-value Liouville theorem, it hence appears to be a good pointwise definition of $K$-quasiregularity. As a corollary of our single-value Reshetnyak’s theorem, we obtain a higher-dimensional version of the argument principle that played a key part in the solution to the Calderón problem. 

   more » « less
5. 𝐿₁-distortion of Wasserstein metrics: A tale of two dimensions

   https://doi.org/10.1090/btran/143  

   Baudier, F.; Gartland, C.; Schlumprecht, Th. (August 2023, Transactions of the American Mathematical Society, Series B)

   By discretizing an argument of Kislyakov, Naor and Schechtman proved that the 1-Wasserstein metric over the planar grid $\{0,1,\dots <\#comment/>,n{\}}^2$has $L_1$-distortion bounded below by a constant multiple of $\sqrt{\log <\#comment/>n}$. We provide a new “dimensionality” interpretation of Kislyakov’s argument, showing that if $\{G_n{\}}_{n=1}^{\mathrm{\infty <\#comment/>}}$is a sequence of graphs whose isoperimetric dimension and Lipschitz-spectral dimension equal a common number $\mathrm{\delta <\#comment/>}\in <\#comment/>[2,\mathrm{\infty <\#comment/>})$, then the 1-Wasserstein metric over $G_n$has $L_1$-distortion bounded below by a constant multiple of $(\log <\#comment/>|G_n|{)}^{\frac{1}{\mathrm{\delta <\#comment/>}}}$. We proceed to compute these dimensions for $\oslash <\#comment/>$-powers of certain graphs. In particular, we get that the sequence of diamond graphs $\{{\mathsf{D}}_n{\}}_{n=1}^{\mathrm{\infty <\#comment/>}}$has isoperimetric dimension and Lipschitz-spectral dimension equal to 2, obtaining as a corollary that the 1-Wasserstein metric over ${\mathsf{D}}_n$has $L_1$-distortion bounded below by a constant multiple of $\sqrt{\log <\#comment/>|{\mathsf{D}}_n|}$. This answers a question of Dilworth, Kutzarova, and Ostrovskii and exhibits only the third sequence of $L_1$-embeddable graphs whose sequence of 1-Wasserstein metrics is not $L_1$-embeddable. 

   more » « less