Experimental realization of a one-way quantum computer algorithm solving Simon's problem

Quantum Simulation Logic, Oracles, and the Quantum Advantage

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 Simon’s 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 Shor’s algorithm for integer factorization.

Experimental characterization of a non-local convertor for quantum photonic networks

We experimentally characterize a quantum photonic gate that is capable of converting multiqubit entangled states while acting only on two qubits. It is an important tool in large quantum networks, where it can be used for re-wiring of multipartite entangled states or for generating various entangled states required for specific tasks. The gate can be also used to generate quantum information processing resources, such as entanglement and discord. In our experimental demonstration, we characterized the conversion of a linear four-qubit cluster state into different entangled states, including GHZ and Dicke states. The high quality of the experimental results show that the gate has the potential of being a flexible component in distributed quantum photonic networks.

Linear optical demonstration of quantum speed-up with a single qudit

Quantum algorithm acts as an important role in quantum computation science, not only for providing a great vision for solving classically unsolvable problems, but also due to the fact that it gives a potential way of understanding quantum physics. We experimentally realize a quantum speed-up algorithm with a single qudit via linear optics and prove that even a single qudit is enough for designing an oracle-based algorithm which can solve a certain problem twice faster than any classical algorithm. The algorithm can be generalized to higher-dimensional systems with the same two-to-one speed-up ratio.

Demonstration of quantum permutation algorithm with a single photon ququart

We report an experiment to demonstrate a quantum permutation determining algorithm with linear optical system. By employing photon's polarization and spatial mode, we realize the quantum ququart states and all the essential permutation transformations. The quantum permutation determining algorithm displays the speedup of quantum algorithm by determining the parity of the permutation in only one step of evaluation compared with two for classical algorithm. This experiment is accomplished in single photon level and the method exhibits universality in high-dimensional quantum computation.