skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on March 27, 2026

Title: On the Computational Hardness of Quantum One-Wayness
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 P N 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 ω ( 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 P P oracle.An interesting implication of our results is that a t ( n ) -copy one-way state generator exists unconditionally, for every t ( n ) = o ( n / log n ) . This contrasts nicely with the previously known fact that O ( n ) -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
Award ID(s):
2016245
PAR ID:
10589815
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
Quantum
Date Published:
Journal Name:
Quantum
Volume:
9
ISSN:
2521-327X
Page Range / eLocation ID:
1679
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an N -dimensional state in depth O ( log ( N ) ) and spacetime allocation (a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) O ( N ) , which are both optimal. When compiled into the { H , S , T , C N O T } gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error ϵ with optimal depth of O ( log ( N ) + log ( 1 / ϵ ) ) and spacetime allocation O ( N log ( log ( N ) / ϵ ) ) , improving over O ( log ( N ) log ( log ( N ) / ϵ ) ) and O ( N log ( N / ϵ ) ) , respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead – O ( N ) ancilla qubits are reused efficiently to prepare a product state of w N -dimensional states in depth O ( w + log ( N ) ) rather than O ( w log ( N ) ) , achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket. 
    more » « less
  2. We report on spectroscopic measurements on the 4 f 7 6 s 2 8 S 7 / 2 ∘<#comment/> →<#comment/> 4 f 7 ( 8 S ∘<#comment/> ) 6 s 6 p ( 1 P ∘<#comment/> ) 8 P 9 / 2 transition in neutral europium-151 and europium-153 at 459.4 nm. The center of gravity frequencies for the 151 and 153 isotopes, reported for the first time in this paper, to our knowledge, were found to be 652,389,757.16(34) MHz and 652,386,593.2(5) MHz, respectively. The hyperfine coefficients for the 6 s 6 p ( 1 P ∘<#comment/> ) 8 P 9 / 2 state were found to be A ( 151 ) = −<#comment/> 228.84 ( 2 ) M H z , B ( 151 ) = 226.9 ( 5 ) M H z and A ( 153 ) = −<#comment/> 101.87 ( 6 ) M H z , B ( 153 ) = 575.4 ( 1.5 ) M H z , which all agree with previously published results except for A(153), which shows a small discrepancy. The isotope shift is found to be 3163.8(6) MHz, which also has a discrepancy with previously published results. 
    more » « less
  3. 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 ∼<#comment/> 98 %<#comment/> for discriminating between the | Ψ<#comment/> + ⟩<#comment/> and | Ψ<#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. We consider minimizing harmonic maps u u from Ω<#comment/> ⊂<#comment/> R n \Omega \subset \mathbb {R}^n into a closed Riemannian manifold N \mathcal {N} and prove: 1. an extension to n ≥<#comment/> 4 n \geq 4 of Almgren and Lieb’s linear law. That is, if the fundamental group of the target manifold N \mathcal {N} is finite, we have\[ H n −<#comment/> 3 ( sing ⁡<#comment/> u ) ≤<#comment/> C ∫<#comment/> ∂<#comment/> Ω<#comment/> | ∇<#comment/> T u | n −<#comment/> 1 d H n −<#comment/> 1 ; \mathcal {H}^{n-3}(\operatorname {sing} u) \le C \int _{\partial \Omega } |\nabla _T u|^{n-1} \,\mathrm {d}\mathcal {H}^{n-1}; \]2. an extension of Hardt and Lin’s stability theorem. Namely, assuming that the target manifold is N = S 2 \mathcal {N}=\mathbb {S}^2 we obtain that the singular set of u u is stable under small W 1 , n −<#comment/> 1 W^{1,n-1} -perturbations of the boundary data. In dimension n = 3 n=3 both results are shown to hold with weaker hypotheses, i.e., only assuming that the trace of our map lies in the fractional space W s , p W^{s,p} with s ∈<#comment/> ( 1 2 , 1 ] s \in (\frac {1}{2},1] and p ∈<#comment/> [ 2 , ∞<#comment/> ) p \in [2,\infty ) satisfying s p ≥<#comment/> 2 sp \geq 2 . We also discuss sharpness. 
    more » « less
  5. We formulate and prove a Conner–Floyd isomorphism for the algebraic K-theory of arbitrary qcqs derived schemes. To that end, we study a stable ∞<#comment/> \infty -category of non- A 1 \mathbb {A}^1 -invariant motivic spectra, which turns out to be equivalent to the ∞<#comment/> \infty -category of fundamental motivic spectra satisfying elementary blowup excision, previously introduced by the first and third authors. We prove that this ∞<#comment/> \infty -category satisfies P 1 \mathbb {P}^1 -homotopy invariance and weighted A 1 \mathbb {A}^1 -homotopy invariance, which we use in place of A 1 \mathbb {A}^1 -homotopy invariance to obtain analogues of several key results from A 1 \mathbb {A}^1 -homotopy theory. These allow us in particular to define a universal oriented motivic E ∞<#comment/> \mathbb {E}_\infty -ring spectrum M G L \mathrm {MGL} . We then prove that the algebraic K-theory of a qcqs derived scheme X X can be recovered from its M G L \mathrm {MGL} -cohomology via a Conner–Floyd isomorphism\[ M G L ∗<#comment/> ∗<#comment/> ( X ) ⊗<#comment/> L Z [ β<#comment/> ±<#comment/> 1 ] ≃<#comment/> K ∗<#comment/> ∗<#comment/> ( X ) , \mathrm {MGL}^{**}(X)\otimes _{\mathrm {L}{}}\mathbb {Z}[\beta ^{\pm 1}]\simeq \mathrm {K}{}^{**}(X), \]where L \mathrm {L}{} is the Lazard ring and K p , q ( X ) = K 2 q −<#comment/> p ( X ) \mathrm {K}{}^{p,q}(X)=\mathrm {K}{}_{2q-p}(X) . Finally, we prove a Snaith theorem for the periodized version of M G L \mathrm {MGL}
    more » « less