IEEE International Conference on Signal, Information and Data Processing (ICSIDP)

Polynomial-time solution for the #P problem based on classical electronic circuits

Jiacheng Bao, Zhenwei Yang, Houjun Sun, Xiangdong Zhang

Published Dec 1, 2019• 0 citations

Abstract

The #P problem is believed to be intractable using classical computers due to difficulties presented by exponential time. It is generally assumed that the best way to solve this problem is to use an algorithm based on quantum mechanics. Here, we propose and demonstrate experimentally an alternative way to solve the #P problem by implementing classical electronic circuits. The typical #P problem to calculate the permanent of a matrix and the related boson sampling problem are solved in polynomial time with exponential frequency bandwidth which limits the scalability of the scheme. The running time of our scheme to solve these problems is equivalent to those based on quantum mechanics. It is also important that our method has good stability of classical circuits. Thus, our findings are advantageous for information processing in the era of big data.

DOI: 10.1109/icsidp47821.2019.9172888

Related papers

Experimental simulation of solution to boson sampling based on classical electronic circuits with exponential frequency bandwidth

Zhenwei Yang, Jiacheng Bao, H. J. Sun +1 more

A Boson sampling device is believed to be a specific quantum computer which is more efficient than its classical counterpart. Recently, a number of experimental realizations have been reported, all were based on multi-photon interference in multimode interferometers. Because of the probabilistic nature of single photons, the technique of coincidence counting has to be used in these schemes, it remains a great challenge to scale up the number of photons. Here, we present a novel way to simulate the solution of the boson sampling problem based on classical electronic circuits. Although an exponential frequency bandwidth is used, thus limiting the scalability of the scheme, the running time of our scheme is equivalent to those based on quantum optics. It is also notable that our method has good stability of classical circuits. In addition, some other related problems, which are computationally hard for classical computers, can also be simulated using our scheme. Thus, our findings are advantageous for information processing in the era of big data.

Europhysics Letters (EPL)Oct 2, 20182 citations

Faster classical boson sampling

Peter Clifford, Raphaël Clifford A

Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.

arXiv:2005.04214Physica ScriptaMay 2, 202421 citations

Efficient computation of permanents, with applications to Boson sampling and random matrices

P. H. Lundow, Klas Markström

In order to find the outcome probabilities of quantum mechanical systems like the optical networks underlying Boson sampling, it is necessary to be able to compute the permanents of unitary matrices, a computationally hard task. Here we first discuss how to compute the permanent efficiently on a parallel computer, followed by algorithms which provide an exponential speed-up for sparse matrices and linear run times for matrices of limited bandwidth. The parallel algorithm has been implemented in a freely available software package, also available in an efficient serial version. As part of the timing runs for this package we set a new world record for the matrix order on which a permanent has been computed. Next we perform a simulation study of several conjectures regarding the distribution of the permanent for random matrices. Here we focus on permanent anti-concentration conjecture, which has been used to find the classical computational complexity of Boson sampling. We find a good agreement with the basic versions of these conjectures, and based on our data we propose refined versions of some of them. For small systems we also find noticeable deviations from a proposed strengthening of a bound for the number of photons in a Boson sampling system.

arXiv:1904.06229Journal of Computational PhysicsJan 19, 202221 citations

Electric-Circuit Realization of Fast Quantum Search

Naiqiao Pan, Tian Chen, Houjun Sun +1 more

Quantum search algorithm, which can search an unsorted database quadratically faster than any known classical algorithms, has become one of the most impressive showcases of quantum computation. It has been implemented using various quantum schemes. Here, we demonstrate both theoretically and experimentally that such a fast search algorithm can also be realized using classical electric circuits. The classical circuit networks to perform such a fast search have been designed. It has been shown that the evolution of electric signals in the circuit networks is analogies of quantum particles randomly walking on graphs described by quantum theory. The searching efficiencies in our designed classical circuits are the same to the quantum schemes. Because classical circuit networks possess good scalability and stability, the present scheme is expected to avoid some problems faced by the quantum schemes. Thus, our findings are advantageous for information processing in the era of big data.

ResearchJan 1, 202130 citations

The Classical Complexity of Boson Sampling

Peter Clifford, Raphaël Clifford A

We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed in STOC ’11 by Aaronson and Arkhipov in 2011 as an attainable demonstration of ‘quantum supremacy’, that is a practical quantum computing experiment able to produce output at a speed beyond the reach of classical (that is non-quantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation. Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level. The fastest known exact classical algorithm for the standard Boson Sampling problem requires time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in time and additional space. The algorithm is simple to implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving near-term quantum supremacy in the context of Boson Sampling.

arXiv:1706.01260Society for Industrial and Applied Mathematics eBooksJan 1, 201826 citations

Classical simulation of boson sampling with sparse output

Wojciech Roga, Masahiro Takeoka

Boson sampling can simulate physical problems for which classical simulations are inefficient. However, not all problems simulated by boson sampling are classically intractable. We show explicit classical methods of finding boson sampling distributions when they are known to be highly sparse. In the methods, we first determine a few distributions from restricted number of detectors and then recover the full one using compressive sensing techniques. In general, the latter step could be of high complexity. However, we show that this problem can be reduced to solving an Ising model which under certain conditions can be done in polynomial time. Various extensions are discussed including a version involving quantum annealing. Hence, our results impact the understanding of the class of classically calculable problems. We indicate that boson samplers may be advantageous in dealing with problems which are not highly sparse. Finally, we suggest a hybrid method for problems of intermediate sparsity.

arXiv:1904.05494Scientific ReportsSep 7, 202010 citations