The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries $U$ such that no quantum polynomial-time oracle algorithm $A^f$ can implement $U$, even approximately, if it only makes one (quantum) query to $f$. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries $A^{f}$. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $A^f$. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.
What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions. Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.
We construct a classically verifiable succinct interactive argument for quantum computation (BQP) with communication complexity and verifier runtime that are poly-logarithmic in the runtime of the BQP computation (and polynomial in the security parameter). Our protocol is secure assuming the post-quantum security of indistinguishability obfuscation (iO) and Learning with Errors (LWE). This is the first succinct argument for quantum computation in the plain model; prior work (Chia-Chung-Yamakawa, TCC '20) requires both a long common reference string and non-black-box use of a hash function modeled as a random oracle. At a technical level, we revisit the framework for constructing classically verifiable quantum computation (Mahadev, FOCS '18). We give a self-contained, modular proof of security for Mahadev's protocol, which we believe is of independent interest. Our proof readily generalizes to a setting in which the verifier's first message (which consists of many public keys) is compressed. Next, we formalize this notion of compressed public keys; we view the object as a generalization of constrained/programmable PRFs and instantiate it based on indistinguishability obfuscation. Finally, we compile the above protocol into a fully succinct argument using a (sufficiently composable) succinct argument of knowledge for NP. Using our framework, we achieve several additional results, including - Succinct arguments for QMA (given multiple copies of the witness), - Succinct non-interactive arguments for BQP (or QMA) in the quantum random oracle model, and - Succinct batch arguments for BQP (or QMA) assuming post-quantum LWE (without iO).
A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problematic in the context of zero-knowledge simulation, where preserving the adversary's state is essential. In this work, we develop new techniques for quantum rewinding in the context of extraction and zero-knowledge simulation: (1) We show how to extract information from a quantum adversary by rewinding it without disturbing its internal state. We use this technique to prove that important interactive protocols, such as the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP, are zero-knowledge against quantum adversaries. (2) We prove that the Goldreich-Kahan protocol for NP is post-quantum zero knowledge using a simulator that can be seen as a natural quantum extension of the classical simulator. Our results achieve (constant-round) black-box zero-knowledge with negligible simulation error, appearing to contradict a recent impossibility result due to Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution: (3) We introduce coherent-runtime expected quantum polynomial time, a computational model that (a) captures all of our zero-knowledge simulators, (b) cannot break any polynomial hardness assumptions, and (c) is not subject to the CCLY impossibility. In light of our positive results and the CCLY negative results, we propose coherent-runtime simulation to be the right quantum analogue of classical expected polynomial-time simulation.
We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.
Lu-Chuan Liu, Luo-Yuan Qu, Cheng Wu, Jordan Cotler, Fei Ma, Ming-Yang Zheng, Xiu-Ping Xie, Yu-Ao Chen, Qiang Zhang, Frank Wilczek, Jian-Wei Pan Interferometers are widely used in imaging technologies to achieve enhanced spatial resolution, but require that the incoming photons be indistinguishable. In previous work, we built and analyzed color erasure detectors which expand the scope of intensity interferometry to accommodate sources of different colors. Here we experimentally demonstrate how color erasure detectors can achieve improved spatial resolution in an imaging task, well beyond the diffraction limit. Utilizing two 10.9 mm-aperture telescopes and a 0.8 m baseline, we measure the distance between a 1063.6 nm source and a 1064.4 nm source separated by 4.2 mm at a distance of 1.43 km, which surpasses the diffraction limit of a single telescope by about 40 times. Moreover, chromatic intensity interferometry allows us to recover the phase of the Fourier transform of the imaged objects - a quantity that is, in the presence of modest noise, inaccessible to conventional intensity interferometry.
We prove that quantum-hard one-way functions imply simulation-secure quantum oblivious transfer (QOT), which is known to suffice for secure computation of arbitrary quantum functionalities. Furthermore, our construction only makes black-box use of the quantum-hard one-way function. Our primary technical contribution is a construction of extractable and equivocal quantum bit commitments based on the black-box use of quantum-hard one-way functions in the standard model. Instantiating the Crépeau-Kilian (FOCS 1988) framework with these commitments yields simulation-secure QOT.
We construct the first constant-round protocols for secure quantum computation in the two-party (2PQC) and multi-party (MPQC) settings with security against malicious adversaries. Our protocols are in the common random string (CRS) model. - Assuming two-message oblivious transfer (OT), we obtain (i) three-message 2PQC, and (ii) five-round MPQC with only three rounds of online (input-dependent) communication; such OT is known from quantum-hard Learning with Errors (QLWE). - Assuming sub-exponential hardness of QLWE, we obtain (i) three-round 2PQC with two online rounds and (ii) four-round MPQC with two online rounds. - When only one (out of two) parties receives output, we achieve minimal interaction (two messages) from two-message OT; classically, such protocols are known as non-interactive secure computation (NISC), and our result constitutes the first maliciously-secure quantum NISC. Additionally assuming reusable malicious designated-verifier NIZK arguments for NP (MDV-NIZKs), we give the first MDV-NIZK for QMA that only requires one copy of the quantum witness. Finally, we perform a preliminary investigation into two-round secure quantum computation where each party must obtain output. On the negative side, we identify a broad class of simulation strategies that suffice for classical two-round secure computation that are unlikely to work in the quantum setting. Next, as a proof-of-concept, we show that two-round secure quantum computation exists with respect to a quantum oracle.
Luo-Yuan Qu, Lu-Chuan Liu, Jordan Cotler, Fei Ma, Jian-Yu Guan, Ming-Yang Zheng, Quan Yao, Xiu-Ping Xie, Yu-Ao Chen, Qiang Zhang, Frank Wilczek, Jian-Wei Pan By developing a `two-crystal' method for color erasure, we can broaden the scope of chromatic interferometry to include optical photons whose frequency difference falls outside of the 400 nm to 4500 nm wavelength range, which is the passband of a PPLN crystal. We demonstrate this possibility experimentally, by observing interference patterns between sources at 1064.4 nm and 1063.6 nm, corresponding to a frequency difference of about 200 GHz.
Mario Motta, Claudio Genovese, Fengjie Ma, Zhi-Hao Cui, Randy Sawaya, Garnet Kin-Lic Chan, Natalia Chepiga, Phillip Helms, Carlos Jimenez-Hoyos, Andrew J. Millis, Ushnish Ray, Enrico Ronca, Hao Shi, Sandro Sorella, Edwin M. Stoudenmire, Steven R. White, Shiwei Zhang Accurate and predictive computations of the quantum-mechanical behavior of many interacting electrons in realistic atomic environments are critical for the theoretical design of materials with desired properties, and require solving the grand-challenge problem of the many-electron Schrodinger equation. An infinite chain of equispaced hydrogen atoms is perhaps the simplest realistic model for a bulk material, embodying several central themes of modern condensed matter physics and chemistry, while retaining a connection to the paradigmatic Hubbard model. Here we report a combined application of cutting-edge computational methods to determine the properties of the hydrogen chain in its quantum-mechanical ground state. Varying the separation between the nuclei leads to a rich phase diagram, including a Mott phase with quasi long-range antiferromagnetic order, electron density dimerization with power-law correlations, an insulator-to-metal transition and an intricate set of intertwined magnetic orders.
By engineering and manipulating quantum entanglement between incoming photons and experimental apparatus, we construct single-photon detectors which cannot distinguish between photons of very different wavelengths. These color erasure detectors enable a new kind of intensity interferometry, with potential applications in microscopy and astronomy. We demonstrate chromatic interferometry experimentally, observing robust interference using both coherent and incoherent photon sources.
Yong Yu, Fei Ma, Xi-Yu Luo, Bo Jing, Peng-Fei Sun, Ren-Zhou Fang, Chao-Wei Yang, Hui Liu, Ming-Yang Zheng, Xiu-Ping Xie, Wei-Jun Zhang, Li-Xing You, Zhen Wang, Teng-Yun Chen, Qiang Zhang, Xiao-Hui Bao, Jian-Wei Pan Quantum internet will enable a number of revolutionary applications. It relies on entanglement of remote quantum memories over long distances. Despite enormous progresses so far, the maximal physical separation achieved between two nodes is 1.3 km, and challenges for long distance remain. Here we make a significant step forward by entangling two atomic ensembles in one lab via photon transmission through metropolitan-scale fibers. We use cavity enhancement to create bright atom-photon entanglement, and harness quantum frequency conversion to shift the atomic wavelength to telecom. We realize entanglement over 22 km field-deployed fibers via two-photon interference, and entanglement over 50 km coiled fibers via single-photon interference. Our experiment can be extended to physically separated nodes with similar distance as a functional segment for atomic quantum networks, thus paving the way towards establishing atomic entanglement over many nodes and over much longer distance.
Mario Motta, David M. Ceperley, Garnet Kin-Lic Chan, John A. Gomez, Emanuel Gull, Sheng Guo, Carlos Jimenez-Hoyos, Tran Nguyen Lan, Jia Li, Fengjie Ma, Andrew J. Millis, Nikolay V. Prokof'ev, Ushnish Ray, Gustavo E. Scuseria, Sandro Sorella, Edwin M. Stoudenmire, Qiming Sun, Igor S. Tupitsyn, Steven R. White, Dominika Zgid, et al (1) We present numerical results for the equation of state of an infinite chain of hydrogen atoms. A variety of modern many-body methods are employed, with exhaustive cross-checks and validation. Approaches for reaching the continuous space limit and the thermodynamic limit are investigated, proposed, and tested. The detailed comparisons provide a benchmark for assessing the current state of the art in many-body computation, and for the development of new methods. The ground-state energy per atom in the linear chain is accurately determined versus bondlength, with a confidence bound given on all uncertainties.
Up-conversion single photon detector (UCSPD) has been widely used in many research fields including quantum key distribution (QKD), lidar, optical time domain reflectrometry (OTDR) and deep space communication. For the first time in laboratory, we have developed an integrated four-channel all-fiber UCSPD which can work in both free-running and gate modes. This compact module can satisfy different experimental demands with adjustable detection efficiency and dark count. We have characterized the key parameters of the UCSPD system.
We study the quantum entanglement and quantum phase transition (QPT) of the anisotropic spin-1/2 XY model with staggered Dzyaloshinskii-Moriya (DM) interaction by means of quantum renormalization group method. The scaling of coupling constants and the critical points of the system are obtained. It is found that when the number of renormalization group iterations tends to infinity, the system exhibit a QPT between the spin-fluid and Néel phases which corresponds with two saturated values of the concurrence for a given value of the strength of DM interaction. The DM interaction can enhance the entanglement and influence the QPT of the system. To gain further insight, the first derivative of the entanglement exhibit a nonanalytic behavior at the critical point and it directly associates with the divergence of the correlation length. This shows that the correlation length exponent is closely related to the critical exponent, i.e., the scaling behaviors of the system.
Jun 10 2005
quant-ph arXiv:quant-ph/0506078v2
Classical statistical average values are generally generalized to average values of quantum mechanics, it is discovered that quantum mechanics is direct generalization of classical statistical mechanics, and we generally deduce both a new general continuous eigenvalue equation and a general discrete eigenvalue equation in quantum mechanics, and discover that a eigenvalue of quantum mechanics is just an extreme value of an operator in possibility distribution, the eigenvalue f is just classical observable quantity. A general classical statistical uncertain relation is further given, the general classical statistical uncertain relation is generally generalized to quantum uncertainty principle, the two lost conditions in classical uncertain relation and quantum uncertainty principle, respectively, are found. We generally expound the relations among uncertainty principle, singularity and condensed matter stability, discover that quantum uncertainty principle prevents from the appearance of singularity of the electromagnetic potential between nucleus and electrons, and give the failure conditions of quantum uncertainty principle. Finally, we discover that the classical limit of quantum mechanics is classical statistical mechanics, the classical statistical mechanics may further be degenerated to classical mechanics, and we discover that only saying that the classical limit of quantum mechanics is classical mechanics is mistake. As application examples, we deduce both Shrodinger equation and state superposition principle, deduce that there exist decoherent factor from a general mathematical representation of state superposition principle, and the consistent difficulty between statistical interpretation of quantum mechanics and determinant property of classical mechanics is overcome.
Braneshop, and
the US National Science Foundation.
SciRate