Search

Grover's unstructured quantum search algorithm gives a quadratic speedup over classical linear search, provided that multiple accesses to the oracle are possible. In this paper, we show that in dealing with NP-complete decision-version problems, the quantum computing paradigm still outperforms classical computation, even if only one invocation of the oracle is allowed. The superiority of the quantum approach under such a restrictive condition can often be maintained even if a simple measurement strategy is chosen. A quantum decider utilizing only Hadamard gates and measurements in the computational basis has a better chance of discriminating between a problem with solution(s) and one without, when compared to the best separation achieved by a classical decider. In addition, the simple quantum measurement strategy is remarkably close to the optimal discriminating measurement, which itself is considerably more complex to devise and implement. If we further require the decider to be unambiguous (any definitive answer must be error-free), then a general positive operator-valued measurement can be devised to classify a problem as unsolvable, with some probability, after one consultation of the oracle. Such a feature remains impossible for a classical decider, even after any less than exhaustive oracle invocations. The inherent probabilistic nature of quantum mechanics seems to be at the heart of the advantage quantum computing exhibits over classical computation, in the context of deciding NP-complete problems based on a single oracle query. [ABSTRACT FROM AUTHOR]

Moving at the speed of light, the photon is the ideal physical support to transmit information. Polarization of a photon is the predominant quantum property used to encode information, but other encoding domains, such as the spatial-mode degree of freedom, have been considered. In this paper, we put forward the entanglement degree of freedom of a photon as an exploitable resource for encoding information in quantum cryptographic protocols. We show how classical information can be extracted from the quantum state of a photon by distinguishing between a singular, independent state and an entangled state through interferometry. We also give a direct application of our technique to quantum key distribution as a proof of concept for future quantum protocols that may use coding in the entanglement domain in combination with other degrees of freedom that are currently exploited for cryptographic purposes. [ABSTRACT FROM AUTHOR]

Quantum bit commitment (QBC) is a quantum version of the classical bit commitment security primitive. As other quantum security primitives and protocols, QBC improves on cheating detection over its classical counterpart. The implementation of the QBC protocol below relies on the use of common quantum gates: the Hadamard gate used for orthonormal bases and the CNOT gate used to swap qubits. The protocol was run and tested on IBM quantum experience (IBM QX). IBM QX offers two different quantum environments: as a simulator and as a real quantum machine. In our implementation, honest and dishonest participants were considered. Results of both the simulation and the quantum execution were compared against the theoretical expectations. The IBM QX simulator gives results that match the theoretical model. The IBM QX real computer deviates from the expected behavior by a measurable amount. Using the standard deviation and the Hamming distance, the conclusion is that the quantum computer is usable as the difference to the simulator is within an acceptable margin of error. The QBC protocol of choice is fully secure against cheating by Bob. The only way Alice can cheat is using multi-dimensional entanglement. The cost for Alice to cheat is exponential in the number of qubits used, namely O (2 6 n + 3 k + 1) . [ABSTRACT FROM AUTHOR]

Together with bit commitment, Oblivious Transfer is a very useful cryptographic primitive with important applications, most notably in secure multiparty computations. It has been long known that secure Quantum Oblivious Transfer can be achieved from a secure implementation of Quantum Bit Commitment. Unfortunately, it is also well known that unconditionally secure Quantum Bit Commitment is impossible, so building a secure Oblivious Transfer protocol on top of Quantum Bit Commitment is ruled out. In this paper, we propose a relatively simple quantum protocol for Oblivious Transfer which does not require qubit storage, does not rely on bit commitment as a primitive and is easily implementable with current technology, if the two actors are honest. The protocol is proven to be secure against any individual measurements and entanglement-based attacks. Any cheating attempt trying to speculate collective measurements would be considerably difficult to put in practice, even in the near future. Furthermore, the number of qubits used in our scheme (embodied as photons in a physical realization of the protocol) acts as a security parameter, making it increasingly hard to cheat. [ABSTRACT FROM AUTHOR]

Current quantum cryptographic protocols aim to distribute a classical secret key to be used afterwards in classical encryption/decryption schemes. We show in this paper that quantum information processing can be used to do much more than just key distribution. Simple quantum transformations augmented with the ability to store qubits in a quantum memory are the building blocks of a class of protocols allowing two parties to communicate secretly by encoding/decoding the exchanged message directly through quantum means, without the need to establish a secret encryption/decryption key first. Consequently, our quantum mechanical process of securely transmitting a message through a public channel is conceptually simpler than the two-step scenario with a quantum distributed classical key. In addition, since the encrypted message is only transmitted through a quantum channel, copying and off-line analysis of the transmission is impossible. Our algorithms rely on the common assumption that public information can be authenticated. In terms of security, the protocol using three encoding bases achieves the maximum detection rate of 33 % per qubit tested. The probability of catching a potential eavesdropper can be brought as close to 1 as desired by increasing the length of the signature string attached to the message. [ABSTRACT FROM AUTHOR]

Security in sensor networks, though an important issue for widely available wireless networks, has been studied less extensively than other properties of these networks, such as, for example, their reliability. The few security schemes proposed so far are based on classical cryptography. In contrast, the present paper develops a new security solution, based on quantum cryptography. The scheme developed here comes with the advantages quantum cryptography has over classical cryptography, namely, effectively unbreakable keys and therefore effectively unconditionally secure messages. Our security system ensures privacy of the measured data field in the presence of an intruder who listens to messages broadcast in the field. [ABSTRACT FROM AUTHOR]