Abstract Demonstrating quantum superiority for some computational task will be a milestone for quantum technologies and would show that computational advantages are possible not only with a universal quantum computer but with simpler physical devices. Linear optics is such a simpler but powerful platform where classically-hard information processing tasks, such as Boson Sampling, can be in principle implemented. In this work, we study a fundamentally different type of computational task to achieve quantum superiority using linear optics, namely the task of verifying NP-complete problems. We focus on a protocol by Aaronson et al. (2008) that uses quantum proofs for verification. We show that the proof states can be implemented in terms of a single photon in an equal superposition over many optical modes. Similarly, the tests can be performed using linear-optical transformations consisting of a few operations: a global permutation of all modes, simple interferometers acting on at most four modes, and measurement using single-photon detectors. We also show that the protocol can tolerate experimental imperfections.
Abstract Demonstrating quantum superiority for some computational task will be a milestone for quantum technologies and would show that computational advantages are possible not only with a universal quantum computer but with simpler physical devices. Linear optics is such a simpler but powerful platform where classically-hard information processing tasks, such as Boson Sampling, can be in principle implemented. In this work, we study a fundamentally different type of computational task to achieve quantum superiority using linear optics, namely the task of verifying NP-complete problems. We focus on a protocol by Aaronson et al. (2008) that uses quantum proofs for verification. We show that the proof states can be implemented in terms of a single photon in an equal superposition over many optical modes. Similarly, the tests can be performed using linear-optical transformations consisting of a few operations: a global permutation of all modes, simple interferometers acting on at most four modes, and measurement using single-photon detectors. We also show that the protocol can tolerate experimental imperfections.
Quantum computing is seeking to realize hardware-optimized algorithms for application-related computational tasks. NP (nondeterministic-polynomial-time) is a complexity class containing many important but intractable problems like the satisfiability of potentially conflict constraints (SAT). According to the well-founded exponential time hypothesis, verifying an SAT instance of size n requires generally the complete solution in an O(n)-bit proof. In contrast, quantum verification algorithms, which encode the solution into quantum bits rather than classical bit strings, can perform the verification task with quadratically reduced information about the solution in [Formula: see text] qubits. Here we realize the quantum verification machine of SAT with single photons and linear optics. By using tunable optical setups, we efficiently verify satisfiable and unsatisfiable SAT instances and achieve a clear completeness-soundness gap even in the presence of experimental imperfections. The protocol requires only unentangled photons, linear operations on multiple modes and at most two-photon joint measurements. These features make the protocol suitable for photonic realization and scalable to large problem sizes with the advances in high-dimensional quantum information manipulation and large scale linear-optical systems. Our results open an essentially new route toward quantum advantages and extend the computational capability of optical quantum computing.
Non-deterministic polynomial (NP)-complete problems are collections of intractable problems for classical computers, but they may be easier to solve for quantum computers. Considering that practical quantum computers and networks are still under development, it is necessary to find alternatives to solve these problems. Simulations with linear optics offer a good choice since much of the research on quantum information is executed with this approach. In this work, based on Aaronson's protocol (Theory Comput, 5, 1, 2009) ad Arrazola et. al.'s linear optics scheme (npj Quantum Inf, 78, 022310, 2018), we present a demonstration of the NP-complete 2-out-of-4 SAT problem for 4 variables. The experimental results show that NP-complete problems can be well simulated through linear optical systems.
In recent years, many computational tasks have been proposed as candidates for showing a quantum computational advantage, that is an advantage in the time needed to perform the task using a quantum instead of a classical machine. Nevertheless, practical demonstrations of such an advantage remain particularly challenging because of the difficulty in bringing together all necessary theoretical and experimental ingredients. Here, we show an experimental demonstration of a quantum computational advantage in a prover-verifier interactive setting, where the computational task consists in the verification of an NP-complete problem by a verifier who only gets limited information about the proof sent by an untrusted prover in the form of a series of unentangled quantum states. We provide a simple linear optical implementation that can perform this verification task efficiently (within a few seconds), while we also provide strong evidence that, fixing the size of the proof, a classical computer would take much longer time (assuming only that it takes exponential time to solve an NP-complete problem). While our computational advantage concerns a specific task in a scenario of mostly theoretical interest, it brings us a step closer to potential useful applications, such as server-client quantum computing.
A universal quantum computer of moderate scale is not available yet, however intermediate models of quantum computation would still permit demonstrations of a quantum computational advantage over classical computing and could challenge the Extended Church-Turing Thesis. One of these models based on single photons interacting via linear optics is called Boson Sampling. Proof-of-principle Boson Sampling has been demonstrated, but the number of photons used for these demonstrations is below the level required to claim quantum computational advantage. To make progress with this problem, here we conclude that the most practically achievable pathway to scale Boson Sampling experiments with current technologies is by combining continuous-variables quantum information and temporal encoding. We propose the use of switchable dual-homodyne and single-photon detections, the temporal loop technique and scattershot based Boson Sampling. This proposal gives details as to what the required assumptions are and a pathway for a quantum optical demonstration of quantum computational advantage. Furthermore, this particular combination of techniques permits a single efficient implementation of Boson Sampling and efficient verification in a single experimental setup.
This dissertation explores the use of single photons in integrated photonic circuits as a platform for quantum computation and quantum simulation. In the noisy intermediate-scale quantum (NISQ) era, photonic implementations of boson sampling provide one of the most promising routes to demonstrating quantum advantage, while also enabling insight-driven experiments that probe many-body interference and computational complexity. The first part of the thesis is devoted to the hardware development and characterization of programmable silicon nitride photonic processors. We demonstrate large-scale multi-photon interference in a 20-mode universal processor, establishing the potential of integrated photonics for scaling up boson sampling experiments. In parallel, we introduce a validation protocol based on detector binning, implemented on a 12-mode predecessor of the device. Together, these studies advance the photonic platform itself, focusing on scalability, versatility, and benchmarking, rather than direct applications. The second part turns to quantum simulation. We first present a photonic simulation of a spin-foam amplitude from loop quantum gravity, illustrating how multi-photon interference can provide a testbed for problems in fundamental physics. We then implement a particle-number-difference Maxwell demon using conditional operations on photon subsets in a multi-mode interferometer. This experiment probes the link between thermodynamics and information theory, showing how a photonic platform with single-photon resolution and quantum interference can be used to explore information-driven control of physical systems. The final part addresses quantum computation, where we demonstrate a boson-sampling-accelerated Monte Carlo integrator. This hybrid quantum–classical algorithm represents one of the few proposals to extend boson sampling toward practical applications while plausibly retaining its computational hardness. We validate the method in a proof-of-principle experiment reproducing perturbative corrections in a model inspired by Efimov physics. Altogether, the results presented in this thesis position integrated photonics as both a scalable hardware platform for multi-photon experiments and a versatile tool for advancing quantum simulation and computation.
Certification is important to guarantee the correct functioning of quantum devices. A key certification task is verifying that a device has produced a desired output state. In this work, we study this task in the context of photonic platforms, where single photons are propagated through linear optical interferometers to create large, entangled resource states for metrology, communication, quantum advantage demonstrations and for so-called linear optical quantum computing (LOQC). This setting derives its computational power from the indistinguishability of the photons, i.e., their relative overlap. Therefore, standard fidelity witnesses developed for distinguishable particles (including qubits) do not apply directly, because they merely certify the closeness to some fixed target state. We introduce a measure of fidelity suitable for this setting and show several different ways to witness it, based on earlier proposals for measuring genuine multi-photon indistinguishability. We argue that a witness based upon the discrete Fourier transform is an optimal choice. We experimentally implement this witness and certify the fidelity of several multi-photon states.