Quantum Supremacy is an expression coined to indicate that there are some hard computational problems that quantum computers can solve exponentially faster than a classical-physical Turing machine (that is, a digital computer). Noise-based Logic (NBL) is a deterministic computation scheme that utilizes a digital computer and a physical true random number generator (TRNG). Recently, several computational problems have been identified where NBL also deterministically offered an exponential speedup compared to a digital computer. In the case of phonebook search, at proper conditions, NBL can even be exponentially faster than Grover's quantum algorithm that offers only a polynomial speedup compared to a digital computer. The newest result is the implementation of the Deutsch-Jozsa problem in NBL. The Deutsch-Jozsa quantum algorithm was historically the first one that was able to offer quantum supremacy. NBL offers the same speedup class. Open philosophical questions emerge about the role of true randomness in the speedup.
Quantum Supremacy is an expression coined to indicate that there are some hard computational problems that quantum computers can solve exponentially faster than a classical-physical Turing machine (that is, a digital computer). Noise-based Logic (NBL) is a deterministic computation scheme that utilizes a digital computer and a physical true random number generator (TRNG). Recently, several computational problems have been identified where NBL also deterministically offered an exponential speedup compared to a digital computer. In the case of phonebook search, at proper conditions, NBL can even be exponentially faster than Grover's quantum algorithm that offers only a polynomial speedup compared to a digital computer. The newest result is the implementation of the Deutsch-Jozsa problem in NBL. The Deutsch-Jozsa quantum algorithm was historically the first one that was able to offer quantum supremacy. NBL offers the same speedup class. Open philosophical questions emerge about the role of true randomness in the speedup.
Instantaneous Noise-Based Logic (INBL) represents a computational paradigm that offers a deterministic alternative to quantum computing, potentially challenging the notion of quantum supremacy without relying on quantum hardware. INBL encodes logical information in orthogonal stochastic processes (“noise-bits”) and exploits their superpositions and nonlinear interactions to achieve an exponentially large computational space of dimension [Formula: see text], where M corresponds to the number of noise-bits analogous to qubits in quantum computing. This approach enables an exponential increase in computational throughput, with a computational speedup scaling on the order of O([Formula: see text], while maintaining hardware complexity comparable to quantum systems. Unlike quantum computers, INBL operates without decoherence, error correction, or probabilistic measurement, yielding deterministic outputs with low error probability. Demonstrated applications include exponential speed-gain compared to classical computers, such as INBL phonebook searches (for number or name lookup) and the implementation of the Deutsch–Jozsa algorithm, illustrating INBL’s capability to perform special-purpose computations with quantum-like exponential speedup using classical-physical noise-based hardware. We present an experimental comparison between the execution speeds of a Classical Turing machine algorithm — which changes the values of odd numbers in an exponentially large set to their next lower even numbers — and its INBL counterpart. Another experimental demonstration of the exponential speedup in finding and removing a given number from an exponentially large, unsorted set of integers.
The original Deutsch–Jozsa (oDJ) problem is for an oracle (realized here as a database) of size N , where, according to their claim, the deterministic solution of the problem on a classical Turing computer requires O( N ) computational complexity. They produced the famous Deutsch–Jozsa quantum algorithm that offered an exponential speed-up over the classical computer, namely O[log( N )] complexity for the solution in a quantum computer. In this paper, the problem is implemented on an instantaneous noise-based logic processor. It is shown that, similarly to the quantum algorithm, the oDJ problem can deterministically be solved with O[log( N )] complexity. The implication is that by adding a truly random coin to a classical Turing machine and using this classical-physical algorithm can also speed up the deterministic solution of the Deutsch–Jozsa problem exponentially, similarly to the quantum algorithm. Then it is realized that the same database and the solution of the Deutsch–Jozsa problem can also be realized by using an identical algorithmic structure in a simpler way, even without noise/random coin. The only lost function in this new system, as compared with noise-based logic, is the ability to do generic parallel logic operations over the whole database. As the latter feature is not needed for the oDJ problem, it is concluded that the problem can be solved on a classical computer with O[log( N )] complexity even without a random coin. Therefore, while the oDJ algorithm is a historically important step in the developments of quantum computers, it is insufficient to prove quantum supremacy. Note, there is also a simplified Deutsch–Jozsa problem proposed later, which is more popular in the field; however, it is irrelevant for the present paper.
Exponential parallelism, a defining principle of advanced computational systems, holds promise for transformative impacts across several scientific and industrial domains. This feature paper provides a comparative overview of Quantum Computing (QC) and Instantaneous Noise-based Logic (INBL), focusing on their practical strengths, limitations and applications rather than exhaustive technical depth. Both paradigms leverage exponentially large Hilbert spaces: QC achieves this via quantum superposition, while INBL realizes it through the product space of classical noise processes. Quantum computers attain universality for all computational operations, whereas current INBL frameworks are universal only for Boolean logic; notably, essential superposition operations — such as AND and OR gates — are absent, precluding implementations of algorithms like Shor’s. However, for certain problem classes where full universality is not required, INBL and QC can offer equivalent time and hardware complexity, as observed with the Deutsch–Jozsa algorithm. Remarkably, for search tasks such as phonebook lookup, Grover’s quantum algorithm provides a quadratic [Formula: see text] speedup compared to the classical approach, while INBL achieves an exponential speedup, requiring only logarithmic time in the size N of the phonebook [Formula: see text]. Such INBL algorithms could, in principle, be adapted to quantum hardware to attain similar performance. Importantly, INBL hardware is considerably simpler, being implementable with modest modifications to conventional PC architectures equipped with a true random number generator, and it inherently avoids the decoherence and error correction challenges of quantum systems.
Exponential parallelism, a defining principle of advanced computational systems, holds promise for transformative impacts across several scientific and industrial domains. This feature paper provides a comparative overview of Quantum Computing (QC) and Instantaneous Noise-based Logic (INBL), focusing on their practical strengths, limitations, and applications rather than exhaustive technical depth. Both paradigms leverage exponentially large Hilbert spaces: quantum computing achieves this via quantum superposition, while INBL realizes it through the product space of classical noise processes. Quantum computers attain universality for all computational operations, whereas current INBL frameworks are universal only for Boolean logic; notably, essential superposition operations-such as AND and OR gates-are absent, precluding implementations of algorithms like Shor's. However, for certain problem classes where full universality is not required, INBL and quantum computing can offer equivalent time and hardware complexity, as observed with the Deutsch-Jozsa algorithm. Remarkably, for search tasks such as phonebook lookup, Grover's quantum algorithm provides a quadratic O(n^0.5) speedup compared to the classical approach, while INBL achieves an exponential speedup, requiring only logarithmic time in the size n of the phonebook O(log n). Such INBL algorithms could, in principle, be adapted to quantum hardware to attain similar performance. Importantly, INBL hardware is considerably simpler, being implementable with modest modifications to conventional PC architectures equipped with a true random number generator, and it inherently avoids the decoherence and error correction challenges of quantum systems.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
We explore the collapse of “wavefunction” and the measurement of entanglement in the superpositions of hyperspace vectors in classical physical instantaneous-noise-based logic (INBL). We find both similarities with and major differences from the related properties of quantum systems. Two search algorithms utilizing the observed features are introduced. For the first one we assume an unsorted names database set up by Alice that is a superposition (unknown by Bob) of up to n = 2N strings; those we call names. Bob has access to the superposition wave and to the 2N reference noises of the INBL system of N noise bits. For Bob, to decide if a given name x is included in the superposition, once the search has begun, it takes N switching operations followed by a single measurement of the superposition wave. Thus, the time and hardware complexity of the search algorithm is O[log(n)], which indicates an exponential speedup compared to Grover’s quantum algorithm in a corresponding setting. An extra advantage is that the error probability of the search is zero. Moreover, the scheme can also check the existence of a fraction of a string, or several separate string fractions embedded in an arbitrarily long, arbitrary string. In the second algorithm, we expand the above scheme to a phonebook with n names and s phone numbers. When the names and numbers have the same bit resolution, once the search has begun, the time and hardware complexity of this search algorithm is O[log(n)]. In the case of one-to-one correspondence between names and phone numbers (n = s), the algorithm offers inverse phonebook search too. The error probability of this search algorithm is also zero.