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.
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.
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.
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.
Quantum computing has changed the paradigm of computer science, where quantum technologies have promised to outperform classical ones. Such an advantage was only demonstrated for tasks with no application or out of reach for the state-of-the-art quantum technologies. In this context, a promising strategy to find practical use of quantum computers exploits hybrid models, where a quantum device estimates a hard-to-compute quantity, while a classical optimizer trains the parameters. In this work, we demonstrate that single photons and linear optical networks are sufficient for implementing variational quantum algorithms, when the problem specification (ansatz) is tailored to this specific platform. We show this by a proof-of-principle demonstration to tackle an instance of a factorization task, whose solution is encoded in the ground state of a suitable Hamiltonian. This work, which combines Variational Quantum Algorithms with hardware efficient ansätze for linear optics, showcases a promising pathway toward practical applications for photonic quantum platforms.
We give a new theoretical solution to a leading-edge experimental challenge, namely to the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in BQP has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional—i.e., it holds even for computationally unbounded provers. Compared to prior work achieving similar results, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted inputs), and show that the random choice between three types of input (defining a computational run, versus two types of test runs) suffices. Because the overhead is very low for each run (it is linear in the size of the circuit), this shows that verification could be achieved at minimal cost compared to performing the computation. As a proof technique, we use a reduction to an entanglement-based protocol; to the best of our knowledge, this is the first time this technique has been used in the context of verification of quantum computations, and it enables a relatively straightforward analysis.
Problems in the class NP are important in computational science, where a given candidate solution can be verified in polynomial time, while finding a solution may require evaluating the entire search space in the worst case. Classical exhaustive approaches generally solve such problems by evaluating the verifier function over all possible inputs, resulting in a worst-case query complexity of O(N), where N = d^n represents the size of the search space, d is the number of possible values for each variable, and n is the number of variables. Quantum search algorithms can solve unstructured search problems more efficiently by reducing the query complexity to O(sqrt (N)), providing a quadratic speedup over classical exhaustive search. However, conventional quantum search formulations typically assume access to an oracle that identifies valid solutions, while standard implementations generally yield probabilistic success. In this work, we propose a generalised quantum oracle construction method for NP problems, together with a deterministic quantum search framework that identifies satisfying assignments using their corresponding classical verifier functions. The proposed framework retains the quadratic query speedup of quantum search over classical exhaustive search. We further establish that constructed oracle can be implemented using a number of gates polynomial in the size (L) of the binary encoding of verification function, consistent with the polynomial-time evaluation of the corresponding classical verifier, while the total qubit requirement remains O(poly(L)). The construction is demonstrated on multiple N-SAT instances, with circuit-level simulations confirming deterministic identification of satisfying assignments. These results establish the applicability of deterministic quantum search to NP problems while retaining the quadratic query advantage over classical exhaustive search.