Experimental Realization of a One-way Quantum Computer Algorithm Solving Simon's Problem
arXiv:1410.3859 · doi:10.1103/PhysRevLett.113.200501
Abstract
We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon's Problem - a black box period-finding problem which has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version's black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon's Problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.
9 pages, 5 figures
References in corpus (27)
- Quantum Cryptography
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Computing
- Photonic quantum technologies
- On the Measurement of Qubits
- Measurement-based quantum computation with cluster states
- Experimental One-Way Quantum Computing
- Measurement-based quantum computation
- High-speed linear optics quantum computing using active feed-forward
- Detecting Genuine Multipartite Entanglement with Two Local Measurements
- Experimental demonstration of a hyper-entangled ten-qubit Schrödinger cat state
- Quantum algorithms for algebraic problems
- Novel schemes for measurement-based quantum computation
- Measurement-based quantum computation beyond the one-way model
- Photonic crystal fibre source of photon pairs for quantum information processing
- Experimental demonstration of a graph state quantum error-correction code
- Experimental Realization of Deutsch's Algorithm in a One-way Quantum Computer
- Measurement-based quantum computation with trapped ions
- Nonclassical 2-photon interference with separate intrinsically narrowband fibre sources
- A scalable, high-speed measurement-based quantum computer using trapped ions
- Experimental characterization of universal one-way quantum computing
- Experimental Realization of the Deutsch-Jozsa Algorithm with a Six-Qubit Cluster State
- Compact Toffoli gate using weighted graph states
- Experimental characterization of photonic fusion using fiber sources
- Experimental Realization of a Four-Photon Seven-Qubit Graph State for One-Way Quantum Computation
- A scalable method for demonstrating the Deutsch-Jozsa and Bernstein-Vazirani algorithms using cluster states
Cited by in corpus (14)
- Deterministic Local Expansion of W States
- Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
- On the effects of self- and cross-phase modulation on photon purity for four-wave mixing photon-pair sources
- OneQ: A Compilation Framework for Photonic One-Way Quantum Computation
- Quantum Simulation Logic, Oracles, and the Quantum Advantage
- Linear optical demonstration of quantum speed-up with a single qudit
- Demonstration of quantum permutation algorithm with a single photon ququart
- Deterministic one-way logic gates on a cloud quantum computer
- Experimental demonstration of a measurement-based realisation of a quantum channel
- Geometry-Based Optimization of One-Way Quantum Computation Measurement Patterns
- Experimental characterization of a non-local convertor for quantum photonic networks
- Coherence and entanglement dynamics in Shor's algorithm
- Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)
- Generalized Type II Fusion of Cluster States