Imagine you're trying to build a lock that doesn't use any metal. You sketch designs, prototype latches from wood and ceramic, and proudly announce a metal-free lock. Then a locksmith walks in with an X-ray and shows you that every design you've tried has a hidden metal pin inside — you just couldn't see it. That's what this paper does to a chunk of the quantum cryptography research program. The committed claim: many existing architectures for pseudorandom quantum states (PRS) and pseudorandom unitaries (PRU) — including constructions explicitly designed to avoid one-way functions — actually imply the existence of one-way functions or NP-hardness. The authors prove this by developing efficient NP-aided shadow tomography for collections of computable pure states, a new algorithmic tool that lets an NP oracle efficiently learn quantum states whose amplitudes and phases are classically computable given their preparation circuits. They extend this to NP-aided learning of unitaries given polynomially many queries. The target is a foundational open question in quantum cryptography sometimes called "Microcrypt": can you build quantum one-wayness and pseudorandomness from assumptions weaker than the existence of (quantum-computable) one-way functions? The dream is a world where quantum mechanics alone provides cryptographic hardness, without needing classical computational assumptions. Only a handful of candidate constructions exist that aren't directly built from one-way functions, and the field has lacked tools to test whether these candidates are secretly smuggling in one-way functions through the back door. The paper's main technical contribution is the NP-aided shadow tomography algorithm. Classical shadow tomography (Aaronson 2018, Huang-Kueng-Preskill 2020) lets you learn properties of quantum states from few copies, but without computational efficiency guarantees for arbitrary state families. This paper shows that if the states are "computable" — meaning amplitudes and phases can be classically efficiently computed from the circuit description — then an NP oracle suffices to make the tomography efficient. This is the X-ray that reveals the hidden metal. The specific casualties are named: Hamiltonian Phase States (Bostanci et al., TQC 2025), which were explicitly introduced to avoid one-way functions, fall to this analysis. The paper shows that PRS and PRU constructions built on computable pure state architectures cannot escape implying one-way functions or NP-hardness. The result doesn't kill the Microcrypt program — it redirects it. Future candidates must use states whose amplitudes and phases are NOT efficiently classically computable, pushing the search toward genuinely quantum-hard structure. The validation is mathematical proof, which is the gold standard for this type of complexity-theoretic result — no simulations or benchmarks to cherry-pick. The arguments build on established shadow tomography techniques and standard complexity-theoretic reductions. The integrity question is whether the "computable pure state" restriction is artificially narrow or captures the constructions people actually care about. The authors argue convincingly that it captures most existing proposals. What remains open is whether non-computable state architectures can deliver PRS/PRU without one-way functions. The paper is explicit that its techniques do not rule out all possible routes to Microcrypt — only the architectures people have actually tried so far. The honest read is that building PRS from genuinely non-computable states is significantly harder, and nobody has a convincing candidate yet. This narrows the search space substantially, which is the kind of negative result that moves a field forward.
