Most research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians, whose ground states can be expressed with only real, nonnegative amplitudes. This raises the question of whether classical Monte Carlo algorithms can efficiently simulate quantum adiabatic optimization with stoquastic Hamiltonians. Recent results have given counterexamples in which path integral and diffusion Monte Carlo fail to do so. However, most adiabatic optimization algorithms, such as for solving MAX-k-SAT problems, use k-local Hamiltonians, whereas our previous counterexample for diffusion Monte Carlo involved n-body interactions. Here we present a new 6-local counterexample which demonstrates that even for these local Hamiltonians there are cases where diffusion Monte Carlo cannot efficiently simulate quantum adiabatic optimization. Furthermore, we perform empirical testing of diffusion Monte Carlo on a standard well-studied class of permutation-symmetric tunneling problems and similarly find large advantages for quantum optimization over diffusion Monte Carlo.

VL - 97 U4 - 022323 UR - https://journals.aps.org/pra/abstract/10.1103/PhysRevA.97.022323 CP - 2 U5 - 10.1103/PhysRevA.97.022323 ER - TY - JOUR T1 - Experimental Low-Latency Device-Independent Quantum Randomness Y1 - 2018 A1 - Yanbao Zhang A1 - Lynden K. Shalm A1 - Joshua C. Bienfang A1 - Martin J. Stevens A1 - Michael D. Mazurek A1 - Sae Woo Nam A1 - Carlos Abellán A1 - Waldimar Amaya A1 - Morgan W. Mitchell A1 - Honghao Fu A1 - Carl A. Miller A1 - Alan Mink A1 - Emanuel Knill AB -Applications of randomness such as private key generation and public randomness beacons require small blocks of certified random bits on demand. Device-independent quantum random number generators can produce such random bits, but existing quantum-proof protocols and loophole-free implementations suffer from high latency, requiring many hours to produce any random bits. We demonstrate device-independent quantum randomness generation from a loophole-free Bell test with a more efficient quantum-proof protocol, obtaining multiple blocks of 512 bits with an average experiment time of less than 5 min per block and with certified error bounded by 2−64≈5.42×10−20.

UR - https://arxiv.org/abs/1812.07786 ER - TY - JOUR T1 - Experimentally Generated Randomness Certified by the Impossibility of Superluminal Signals JF - Nature Y1 - 2018 A1 - Peter Bierhorst A1 - Emanuel Knill A1 - Scott Glancy A1 - Yanbao Zhang A1 - Alan Mink A1 - Stephen Jordan A1 - Andrea Rommal A1 - Yi-Kai Liu A1 - Bradley Christensen A1 - Sae Woo Nam A1 - Martin J. Stevens A1 - Lynden K. Shalm AB -From dice to modern complex circuits, there have been many attempts to build increasingly better devices to generate random numbers. Today, randomness is fundamental to security and cryptographic systems, as well as safeguarding privacy. A key challenge with random number generators is that it is hard to ensure that their outputs are unpredictable. For a random number generator based on a physical process, such as a noisy classical system or an elementary quantum measurement, a detailed model describing the underlying physics is required to assert unpredictability. Such a model must make a number of assumptions that may not be valid, thereby compromising the integrity of the device. However, it is possible to exploit the phenomenon of quantum nonlocality with a loophole-free Bell test to build a random number generator that can produce output that is unpredictable to any adversary limited only by general physical principles. With recent technological developments, it is now possible to carry out such a loophole-free Bell test. Here we present certified randomness obtained from a photonic Bell experiment and extract 1024 random bits uniform to within 10−12. These random bits could not have been predicted within any physical theory that prohibits superluminal signaling and allows one to make independent measurement choices. To certify and quantify the randomness, we describe a new protocol that is optimized for apparatuses characterized by a low per-trial violation of Bell inequalities. We thus enlisted an experimental result that fundamentally challenges the notion of determinism to build a system that can increase trust in random sources. In the future, random number generators based on loophole-free Bell tests may play a role in increasing the security and trust of our cryptographic systems and infrastructure.

VL - 556 U4 - 223-226 UR - https://arxiv.org/abs/1803.06219 U5 - https://doi.org/10.1038/s41586-018-0019-0 ER - TY - JOUR T1 - Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling Y1 - 2017 A1 - Peter Bierhorst A1 - Emanuel Knill A1 - Scott Glancy A1 - Alan Mink A1 - Stephen P. Jordan A1 - Andrea Rommal A1 - Yi-Kai Liu A1 - Bradley Christensen A1 - Sae Woo Nam A1 - Lynden K. Shalm AB -Random numbers are an important resource for applications such as numerical simulation and secure communication. However, it is difficult to certify whether a physical random number generator is truly unpredictable. Here, we exploit the phenomenon of quantum nonlocality in a loophole-free photonic Bell test experiment for the generation of randomness that cannot be predicted within any physical theory that allows one to make independent measurement choices and prohibits superluminal signaling. To certify and quantify the randomness, we describe a new protocol that performs well in an experimental regime characterized by low violation of Bell inequalities. Applying an extractor function to our data, we obtained 256 new random bits, uniform to within 0.001.

UR - https://arxiv.org/abs/1702.05178# ER -