Building generic gates from a restricted gate set is a difficult but important problem, especially in the noisy regime where only a limited set of noise-resistant gates are available, e.g., fault-tolerant Clifford gates (generated by Hadamard, phase, and cnot gates) and fault-tolerant Toffoli gates. The Toffoli is also often used as a building block of many algorithms and will need to be constructed if not directly available. This makes Clifford+Toffoli an attractive gate set for building generic gates. In this Letter we give a simple and efficient algorithm for building an approximate single-qubit rotation using only Clifford+Toffoli, which in turn enables any generic single-qubit unitary. An important difference compared to earlier attempts is that the use of the Toffoli allows us to use simple rounding as opposed to a complicated approximation algorithm. The resulting gate array does not rely on repeatedly applying a fixed rotation, but immediately applies a rotation 𝑅𝜃* that is 𝜀-close to the desired rotation 𝑅𝜃, with a success probability strictly greater than 1/2. It can be rerun upon failure, giving an expected number of repetitions strictly less than 2, an expected Toffoli count strictly less than 4⁢⌈log⁡1𝜀⌉, an expected gate depth strictly less than 4⁢⌈log⁡1𝜀⌉+6, and uses 2⁢⌈log⁡1𝜀⌉ ancillas. The small circuit depth of our construction enables low-noise gates on existing quantum computational devices, and allows for arbitrary precision using a very modest number of ancillas.

We propose a conjugate logic that can capture the behavior of quantum and quantum-like systems. The proposal is similar to the more generic concept of epistemic logic: it encodes knowledge or perhaps more correctly, predictions about outcomes of future observations on some systems. For a quantum system, these predictions are statements about future outcomes of measurements performed on specific degrees of freedom of the system. The proposed logic will include propositions and their relations, including connectives, but importantly also transformations between propositions on conjugate degrees of freedom of the systems. A key point is the addition of a transformation that allows to convert propositions about single systems into propositions about correlations between systems. We will see that subtle choices of the properties of the transformations lead to drastically different underlying mathematical models; one choice gives stabilizer quantum mechanics, while another choice gives Spekkens’ toy theory. This points to a crucial basic property of quantum and quantum-like systems that can be handled within the present conjugate logic by adjusting the mentioned choice. It also enables a discussion on what behaviors are properly quantum or only quantum-like, relating to that choice and how it manifests in the system under scrutiny. 

Query complexity is a common tool for comparing quantum and classical computation, and it has produced many examples of how quantum algorithms differ from classical ones. Here we investigate in detail the role that oracles play for the advantage of quantum algorithms. We do so by using a simulation framework, Quantum Simulation Logic (QSL), to construct oracles and algorithms that solve some problems with the same success probability and number of queries as the quantum algorithms. The framework can be simulated using only classical resources at a constant overhead as compared to the quantum resources used in quantum computation. Our results clarify the assumptions made and the conditions needed when using quantum oracles. Using the same assumptions on oracles within the simulation framework we show that for some specific algorithms, such as the Deutsch-Jozsa and Simons algorithms, there simply is no advantage in terms of query complexity. This does not detract from the fact that quantum query complexity provides examples of how a quantum computer can be expected to behave, which in turn has proved useful for finding new quantum algorithms outside of the oracle paradigm, where the most prominent example is Shors algorithm for integer factorization.

A Bell test is a randomized trial that compares experimental observations against the philosophical worldview of local realism , in which the properties of the physical world are independent of our observation of them and no signal travels faster than light. A Bell test requires spatially distributed entanglement, fast and high-efficiency detection and unpredictable measurement settings. Although technology can satisfy the first two of these requirements, the use of physical devices to choose settings in a Bell test involves making assumptions about the physics that one aims to test. Bell himself noted this weakness in using physical setting choices and argued that human 'free will' could be used rigorously to ensure unpredictability in Bell tests. Here we report a set of local-realism tests using human choices, which avoids assumptions about predictability in physics. We recruited about 100,000 human participants to play an online video game that incentivizes fast, sustained input of unpredictable selections and illustrates Bell-test methodology. The participants generated 97,347,490 binary choices, which were directed via a scalable web platform to 12 laboratories on five continents, where 13 experiments tested local realism using photons, single atoms, atomic ensembles and superconducting devices. Over a 12-hour period on 30 November 2016, participants worldwide provided a sustained data flow of over 1,000 bits per second to the experiments, which used different human-generated data to choose each measurement setting. The observed correlations strongly contradict local realism and other realistic positions in bi-partite and tri-partite 12 scenarios. Project outcomes include closing the 'freedom-of-choice loophole' (the possibility that the setting choices are influenced by 'hidden variables' to correlate with the particle properties), the utilization of video-game methods for rapid collection of human-generated randomness, and the use of networking techniques for global participation in experimental science.

In a recent Letter [Phys. Rev. Lett. 118, 030501 (2017)], Peiris, Konthasinghe, and Muller report a Franson interferometry experiment using pairs of photons generated from a two-level semiconductor quantum dot. The authors report a visibility of 66% and claim that this visibility “goes beyond the classical limit of 50% and approaches the limit of violation of Bell’s inequalities (70.7%).” We explain why we do not agree with this last statement and how to fix the problem.

Bell inequality tests of local realism are notoriously difficult to perform. Physicists have attempted these tests for more than 50 years, and for each attempt, gotten closer and closer to a proper test. So far, every test performed has been riddled by one or more loopholes. 

We demonstrate how adversaries with unbounded computing resources can break Quantum Key Distribution (QKD) protocols which employ a particular message authentication code suggested previously. This authentication code, featuring low key consumption, is not Information-Theoretically Secure (ITS) since for each message the eavesdropper has intercepted she is able to send a different message from a set of messages that she can calculate by finding collisions of a cryptographic hash function. However, when this authentication code was introduced it was shown to prevent straightforward Man-In-The-Middle (MITM) attacks against QKD protocols.

In this paper, we prove that the set of messages that collide with any given message under this authentication code contains with high probability a message that has small Hamming distance to any other given message. Based on this fact we present extended MITM attacks against different versions of BB84 QKD protocols using the addressed authentication code; for three protocols we describe every single action taken by the adversary. For all protocols the adversary can obtain complete knowledge of the key, and for most protocols her success probability in doing so approaches unity.

Since the attacks work against all authentication methods which allow to calculate colliding messages, the underlying building blocks of the presented attacks expose the potential pitfalls arising as a consequence of non-ITS authentication in QKDpostprocessing. We propose countermeasures, increasing the eavesdroppers demand for computational power, and also prove necessary and sufficient conditions for upgrading the discussed authentication code to the ITS level.

Everyday experience supports the existence of physical properties independent of observation in strong contrast to the predictions of quantum theory. In particular, the existence of physical properties that are independent of the measurement context is prohibited for certain quantum systems. This property is known as contextuality. This Rapid Communication studies whether the process of decay in space-time generally destroys the ability of revealing contextuality. We find that in the most general situation the decay property does not diminish this ability. However, applying certain constraints due to the space-time structure either on the time evolution of the decaying system or on the measurement procedure, the criteria revealing contextuality become inherently dependent on the decay property or an impossibility. In particular, we derive how the context-revealing setup known as Bells nonlocality tests changes for decaying quantum systems. Our findings illustrate the interdependence between hidden and local hidden parameter theories and the role of time.

Experimental violations of Bell inequalities are in general vulnerable to so-called loopholes. In this work, we analyze the characteristics of a loophole-free Bell test with photons, closing simultaneously the locality, freedom-of-choice, fair-sampling (i.e., detection), coincidence-time, and memory loopholes. We pay special attention to the effect of excess predictability in the setting choices due to nonideal random-number generators. We discuss necessary adaptations of the Clauser-Horne and Eberhard inequality when using such imperfect devices and-using Hoeffdings inequality and Doobs optional stopping theorem-the statistical analysis in such Bell tests.

We present a formal theory of contextuality for a set of random variables grouped into different subsets (contexts) corresponding to different, mutually incompatible conditions. Within each context the random variables are jointly distributed, but across different contexts they are stochastically unrelated. The theory of contextuality is based on the analysis of the extent to which some of these random variables can be viewed as preserving their identity across different contexts when one considers all possible joint distributions imposed on the entire set of the random variables. We illustrate the theory on three systems of traditional interest in quantum physics (and also in non-physical, e.g., behavioral studies). These are systems of the Klyachko-Can-Binicioglu-Shumovsky-type, Einstein-Podolsky-Rosen-Bell-type, and Suppes-Zanotti-Leggett-Garg-type. Listed in this order, each of them is formally a special case of the previous one. For each of them we derive necessary and sufficient conditions for contextuality while allowing for experimental errors and contextual biases or signaling. Based on the same principles that underly these derivations we also propose a measure for the degree of contextuality and compute it for the three systems in question.