Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The Very True Theoretical Ultimate Algorithm for Quantum Computers

Koji Nagata, Tadao Nakamura

Published Mar 1, 2019• 0 citations
OpenAlex

Abstract

Here, we propose a new type of quantum algorithm for determining the $2^N$ values of a function. By measuring the single output state, we determine all the values of $f(x)$ for all $x$ simultaneously. This is very interesting indeed: the quantum circuit gives us the ability to determine a perfect property of $f(x)$, namely, $f(x)$. This is faster than a classical apparatus by a factor of $2^N$.

Related papers

Quantum Cryptography Through Some Algorithm for Quantum Computers

Koji Nagata, Do Ngoc Diep, Tadao Nakamura

We propose quantum cryptography based on an algorithm of determining a function. The security of our cryptography is based on the Ekert 1991 protocol, that is, we use an entangled state. Eve must destroy the entangled state. Consider a function. Alice knows all the mappings concerning the function. Bob knows none of them. His aim is of obtaining all of them without Eve's attack. In classical case, Bob needs some queries. In quantum case, Bob needs just a query. By measuring the single entangled state, which is sent by Alice, Bob can obtain all the mappings concerning the function, simultaneously. This is faster than classical cryptography.

•Jan 1, 2020•0 citations

A Method of Computing Many Functions Simultaneously by Using Many Parallel Quantum Systems

Koji Nagata, Germano Resconi, Tadao Nakamura +4 more

We suggest a method of computing many functions in the same time by using many parallel quantum systems. We use the Bernstein-Vazirani algorithm. Given the set of real values $\{a_1,a_2,a_3,\ldots,a_N\}$, and the function $g:{\bf R}\rightarrow \{0,1\}$, we shall determine the following values $\{g(a_1),g(a_2),g(a_3),\ldots, g(a_N)\}$ simultaneously. By using $M$ parallel quantum systems, we can compute $M$ functions $g^1,g^2,...,g^M$ simultaneously. The speed of determining the $N\times M$ values will be shown to outperform the classical case by a factor of $N$.

•Apr 1, 2017•1 citation

Quantum supremacy: some fundamental concepts

Man‐Hong Yung

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!

National Science Review•Jul 4, 2018•24 citations

Bulk spin quantum computation: toward large-scale quantum computation

Isaac L. Chuang, Lieven M. K. Vandersypen, J. S. Harris

Quantum computation offers the potential for solving specific problems exponentially faster than the best classical machines, by virtue of its non-classical dynamics and information representation. Quantum mechanical bits (called 'qubits') can be both 0 and 1 at the same time, in which case the qubit is said to be in a superposition state. A quantum gate with input 0 or 1 gives the same output as a classical gate, but if the input is 0 and 1 simultaneously, the quantum gate performs the two corresponding operations simultaneously. Similarly, a 2-qubit gate with an input state prepared as a superposition of the 4 combinations 00, 01, 10 and 11, performs four simultaneous computations. In general, an N-qubit gate could perform 2/sup N/ computations at the same time. So as we increase the size of the system, the computational capacity of the apparatus goes up exponentially, compared to linearly for a classical computer. Using commercial NMR-spectrometers, simple quantum circuits are experimentally implemented consisting of multiple cascaded logic gates.

Digest of technical papers/Digest of technical papers - IEEE International Solid-State Circuits Conference•Nov 27, 2002•2 citations

Ultimate Algorithm for Quantum Computers

Koji Nagata, Tadao Nakamura

We first propose herein a novel parallel computation, even though today's algorithm methodology for quantum computing, for all of the combinations of values in variables of a logical function. Our concern so far has been to obtain an attribute of some function. In fact such a task is only for one task problem solving. However, we could treat positively the plural evaluations of some logic function in parallel instead of testing the function for finding out its attribute. In fact, these evaluations of the function are naturally included and evaluated, in parallel, in normal quantum computing discussing a function in a Boolean algebra stemmed from atoms in it. As is naturally understandable with mathematics, quantum computing with qubit systems naturally is included and exemplified by a Boolean algebra, which treats only both 0 and 1. Namely, the theory in this paper is quite natural in logical sense even though physics domain. Therefore, quantum computing has an ability to solve some mathematical problems described in a Boolean algebra. The reason why we positively introduce a Boolean algebra here is because we have multiple evaluations of a function in quantum computing general.

•Mar 1, 2019•0 citations

CHARACTERISTICS OF QUANTUM CIRCUITS WITH FUNCTIONAL CONFIGURATIONS OF QUBITS

S.M. Gushanskiy, V.S. Potapov

The paper is an exploration of a new approach to the systematic analysis and classificationof quantum circuits based on the functional configuration of qubits. The article examines in detailthe role of elementary gates in changing the elements of the state vector and highlights the importanceof functional configurations of qubits in the collective modification of quantum states.The main aspects covered in the article include the characterization of quantum circuits with functionalconfigurations of qubits, analysis of the impact of elementary gates on the state of a quantumvector, and determination of the number of possible types of functional configurations.The results of the study could have important implications for optimizing quantum circuits andimproving our understanding of their general properties. A qubit functional configuration is amathematical structure that can collectively classify the properties and behavior of quantum circuits.The development of quantum algorithms with efficient quantum circuits has been a centralpart of quantum computing, which has seen enormous progress both theoretically and experimentallyover the past 30 years. The paper makes a contribution to the field of quantum computing byproviding a systematic approach to classify and analyze quantum circuits based on their functionalqubit configurations. Quantum algorithms are an innovative class of algorithms based on theprinciples of quantum mechanics and using qubits instead of classical bits to process information.Unlike classical algorithms, which operate on bits that take on the values 0 or 1, quantum algorithmscan use the principles of quantum superposition and quantum interaction, which allowsthem to perform many calculations simultaneously. One of the key advantages of quantum algorithmsis their ability to solve certain problems much more efficiently than classical algorithms.However, the design and implementation of quantum algorithms pose significant technical andalgorithmic challenges, such as managing quantum states, minimizing errors, and creating robustquantum gates. Despite these challenges, quantum algorithms offer promising opportunities torevolutionize computing and solve problems that have traditionally been too complex for classicalcomputers

Известия Южного федерального университета. Технические науки•Dec 29, 2023•1 citation
Here, we propose a new type of quantum algorithm for determining the 2N2^N2N values of a function. By measuring the single output state, we determine all the values of f(x)f(x)f(x) for all xxx simultaneously. This is very interesting indeed: the quantum circuit gives us the ability to determine a perfect property of f(x)f(x)f(x), namely, f(x)f(x)f(x). This is faster than a classical apparatus by a factor of 2N2^N2N.
We propose quantum cryptography based on an algorithm of determining a function. The security of our cryptography is based on the Ekert 1991 protocol, that is, we use an entangled state. Eve must destroy the entangled state. Consider a function. Alice knows all the mappings concerning the function. Bob knows none of them. His aim is of obtaining all of them without Eve's attack. In classical case, Bob needs some queries. In quantum case, Bob needs just a query. By measuring the single entangled state, which is sent by Alice, Bob can obtain all the mappings concerning the function, simultaneously. This is faster than classical cryptography.
We suggest a method of computing many functions in the same time by using many parallel quantum systems. We use the Bernstein-Vazirani algorithm. Given the set of real values {a1,a2,a3,…,aN}\{a_1,a_2,a_3,\ldots,a_N\}{a1​,a2​,a3​,…,aN​}, and the function g:R→{0,1}g:{\bf R}\rightarrow \{0,1\}g:R→{0,1}, we shall determine the following values {g(a1),g(a2),g(a3),…,g(aN)}\{g(a_1),g(a_2),g(a_3),\ldots, g(a_N)\}{g(a1​),g(a2​),g(a3​),…,g(aN​)} simultaneously. By using MMM parallel quantum systems, we can compute MMM functions g1,g2,...,gMg^1,g^2,...,g^Mg1,g2,...,gM simultaneously. The speed of determining the N×MN\times MN×M values will be shown to outperform the classical case by a factor of NNN.
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!
Quantum computation offers the potential for solving specific problems exponentially faster than the best classical machines, by virtue of its non-classical dynamics and information representation. Quantum mechanical bits (called 'qubits') can be both 0 and 1 at the same time, in which case the qubit is said to be in a superposition state. A quantum gate with input 0 or 1 gives the same output as a classical gate, but if the input is 0 and 1 simultaneously, the quantum gate performs the two corresponding operations simultaneously. Similarly, a 2-qubit gate with an input state prepared as a superposition of the 4 combinations 00, 01, 10 and 11, performs four simultaneous computations. In general, an N-qubit gate could perform 2/sup N/ computations at the same time. So as we increase the size of the system, the computational capacity of the apparatus goes up exponentially, compared to linearly for a classical computer. Using commercial NMR-spectrometers, simple quantum circuits are experimentally implemented consisting of multiple cascaded logic gates.
We first propose herein a novel parallel computation, even though today's algorithm methodology for quantum computing, for all of the combinations of values in variables of a logical function. Our concern so far has been to obtain an attribute of some function. In fact such a task is only for one task problem solving. However, we could treat positively the plural evaluations of some logic function in parallel instead of testing the function for finding out its attribute. In fact, these evaluations of the function are naturally included and evaluated, in parallel, in normal quantum computing discussing a function in a Boolean algebra stemmed from atoms in it. As is naturally understandable with mathematics, quantum computing with qubit systems naturally is included and exemplified by a Boolean algebra, which treats only both 0 and 1. Namely, the theory in this paper is quite natural in logical sense even though physics domain. Therefore, quantum computing has an ability to solve some mathematical problems described in a Boolean algebra. The reason why we positively introduce a Boolean algebra here is because we have multiple evaluations of a function in quantum computing general.
The paper is an exploration of a new approach to the systematic analysis and classificationof quantum circuits based on the functional configuration of qubits. The article examines in detailthe role of elementary gates in changing the elements of the state vector and highlights the importanceof functional configurations of qubits in the collective modification of quantum states.The main aspects covered in the article include the characterization of quantum circuits with functionalconfigurations of qubits, analysis of the impact of elementary gates on the state of a quantumvector, and determination of the number of possible types of functional configurations.The results of the study could have important implications for optimizing quantum circuits andimproving our understanding of their general properties. A qubit functional configuration is amathematical structure that can collectively classify the properties and behavior of quantum circuits.The development of quantum algorithms with efficient quantum circuits has been a centralpart of quantum computing, which has seen enormous progress both theoretically and experimentallyover the past 30 years. The paper makes a contribution to the field of quantum computing byproviding a systematic approach to classify and analyze quantum circuits based on their functionalqubit configurations. Quantum algorithms are an innovative class of algorithms based on theprinciples of quantum mechanics and using qubits instead of classical bits to process information.Unlike classical algorithms, which operate on bits that take on the values 0 or 1, quantum algorithmscan use the principles of quantum superposition and quantum interaction, which allowsthem to perform many calculations simultaneously. One of the key advantages of quantum algorithmsis their ability to solve certain problems much more efficiently than classical algorithms.However, the design and implementation of quantum algorithms pose significant technical andalgorithmic challenges, such as managing quantum states, minimizing errors, and creating robustquantum gates. Despite these challenges, quantum algorithms offer promising opportunities torevolutionize computing and solve problems that have traditionally been too complex for classicalcomputers