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

arXiv:1707.05660 · NeuroQuantology

Quantum Computation via Sparse Distributed Representation

Gerard J. Rinkus

Published Jun 1, 2012• 5 citations
arXivHTMLPDF

Abstract

Quantum superposition says that any physical system simultaneously exists in all of its possible states, the number of which is exponential in the number of entities composing the system. The strength of presence of each possible state in the superposition, i.e., its probability of being observed, is represented by its probability amplitude coefficient. The assumption that these coefficients must be represented physically disjointly from each other, i.e., localistically, is nearly universal in the quantum theory/computing literature. Alternatively, these coefficients can be represented using sparse distributed representations (SDR), wherein each coefficient is represented by small subset of an overall population of units, and the subsets can overlap. Specifically, I consider an SDR model in which the overall population consists of Q WTA clusters, each with K binary units. Each coefficient is represented by a set of Q units, one per cluster. Thus, K^Q coefficients can be represented with KQ units. Thus, the particular world state, X, whose coefficient's representation, R(X), is the set of Q units active at time t has the max probability and the probability of every other state, Y_i, at time t, is measured by R(Y_i)'s intersection with R(X). Thus, R(X) simultaneously represents both the particular state, X, and the probability distribution over all states. Thus, set intersection may be used to classically implement quantum superposition. If algorithms exist for which the time it takes to store (learn) new representations and to find the closest-matching stored representation (probabilistic inference) remains constant as additional representations are stored, this meets the criterion of quantum computing. Such an algorithm has already been described: it achieves this "quantum speed-up" without esoteric hardware, and in fact, on a single-processor, classical (Von Neumann) computer.

DOI
10.14704/nq.2012.10.2.507

Related papers

On Quantum Computation

Mika Hirvensalo

As early as 1982 Richard P. Feynman suggested that it might be impossible to simulate quantum mechanical phenomena with a computer without an exponential slowdown the efficiency of computation. He also proposed that this problem may be avoided by allowing the computer to run according to the laws of quantum mechanics, thus implicitely suggesting that a computer based on the quantum mechanical systems, a quantum computer, might have exponentially more computational efficiency than any classical one. A quantum mechanical phenomenon that never occurs classical physics and which actually makes quantum computation interesting and powerful, is the superposition of states, which, loosely speaking, means that instead of being totally one single state, a particle can be in between many states. Compare this to the elements of classical computer, bits. A bit takes values zero or one, but never anything between. In a quantum computer, one is able to store it both values simultaneously one quantum bit, equally weighted or not. Moreover, the classical computer one can store a number from zero to $2^n-1$ a register of length $n$, whereas, quantum computation, all the values could be stored simultaneously. The computation, which is performed via unitary transformations the state vector space, then applies to all these values simultaneously. Thus the power of the quantum computation lies not the absolute speed of the hypothetetical quantum computer but the possibility to actually follow many computational path simultaneously, as a nondeterministic automaton does. Alas, the observation of the outcome will yield only one value destroying the rest irreversibly. However, using a procedure smart enough one could obtain some valuable information about the computation.

•May 14, 1997•4 citations

Resource-efficient quantum data representation based on Grover’s algorithm

Jaewon Ji, Joonho Bae

The superposition state of qubits in quantum computers enables a more efficient data representation than conventional binary methods in classical computers. Grover’s algorithm amplifies the amplitude of a target state within a superposed set of states having equal amplitudes. However, except for a 2-qubit system, the amplitudes of the nontarget states and left residual amplitudes induced by the algorithm do not reduce to zero. Therefore, a new method was devised to overcome this drawback. We select new target state among the nontarget states by applying Grover’s algorithm and obtain two distinct states with different amplitudes. Consequently, by excluding duplicate cases, this method enables the representation of [Formula: see text] data points. This technique is referred to as superdense data representation (SDR). Specifically, SDR is a new data representation method for quantum computers using superposition and entanglement. This offers several advantages for encoding data. For instance, 8-qubit data can be effectively represented in 4-qubit, thereby reducing the resources required to store the information. Additionally, SDR allows the representation of more complex data, such as Unicode, without increasing calculation or storage costs. UTF-8 encoding method can be implemented using only eight qubits. By extending SDR, Asian languages that require more than two bytes of data can also be expressed using eight qubits.

International Journal of Quantum Information•Jul 30, 2025•0 citations

5 Four myths about quantum computing

Koen Groenland

Four myths about quantum computingThis chapter relies on a bit of quantum physics jargon.See the chapter 'An introduction to the quantum world' for a quick introduction. Myth 1: Quantum computers find all solutions at onceThis myth is likely the most technical, and builds on a misinterpretation of the concept of superposition.A single qubit can be in two states at the same time (0 and 1), two qubits can represent four states (00, 01, 10, 11), and three qubits are potentially in eight unique configurations simultaneously.As we increase the number of qubits, this number of coexisting states scales exponentially!This means that a mere 1000 qubits can effectively 'store' 2 1000 unique values, all at the same time.That's an incomprehensibly large number, much more than there are atoms in the visible universe.Even the fastest computers in the world couldn't loop through all these states in a lifetime.Each of these states can be interpreted like a file on a computer, be it an Excel spreadsheet, a web page, a CAD drawing, or whatever kind of data we choose to work with.A smart computer scientist can also devise a way to make 1000 bits represent 'solutions' to a problem.For example, imagine that we want to find an optimal aeroplane wing that generates incredible lift while requiring as few materials as possible.Using quantum superposition, we might represent 2 1000 such wings simultaneously.We picked the example of aeroplane wings because simulating their aerodynamic properties requires a pretty hefty computation.Let's assume that we have written such a computer program that accurately simulates any wing.Let's call that program f .It will output 1 if the wing works well (according to whatever metric), and 0 otherwise.Surely, the program takes a very large number of computation steps, which we'll call T. The program will need some input, denoted by x , which is a 1000-bit description of all the relevant properties of a hypothetical aeroplane wing.In other words, the computer program computes f (x) = 1 if x is a fantastic wing, and f (x) = 0 if it's rubbish.Now, a quantum computer should be able to execute any classical function, right?We should be able to run f on a quantum computer, but now we have the unique feature that the 1000-qubit input can represent a humongous number of potential aeroplane wings at the same time.By doing a mere T computational steps, we can check the properties of 2 1000 solutions!

Amsterdam University Press eBooks•Mar 9, 2025•0 citations

Quantum Computation

David Peter Divincenzo

If the bits of computers are someday scaled down to the size of individual atoms, quantum mechanical effects may profoundly change the nature of computation itself. The wave function of such a quantum computer could consist of a superposition of many computations carried out simultaneously; this kind of parallelism could be exploited to make some important computational problems, like the prime factoring of large integers, tractable. However, building such a quantum computer would place undreamed of demands on the experimental realization of highly quantum-coherent systems; present-day experimental capabilities in atomic physics and other fields permit only the most rudimentary implementation of quantum computation.

Science•Oct 13, 1995•1,655 citations

Simulating Quantum Circuits with Sparse Output Distributions

Martin Schwarz, Maarten Van den Nest

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor's factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation is an efficient algorithm for approximating the significant Fourier coefficients of a class of states called computationally tractable states. The latter result may have applications beyond the scope of this work. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.

arXiv:1310.6749•Electronic colloquium on computational complexity•Oct 24, 2013•45 citations

Von Neumann’s theory, projective measurement, and quantum computation

Koji Nagata, Tadao Nakamura

We discuss the fact that there is a crucial contradiction within Von Neumann's theory. We derive a proposition concerning a quantum expected value under an assumption of the existence of the orientation of reference frames in $N$ spin-1/2 systems ($1 \leq N < +\infty$). This assumption intuitively depictures our physical world. However, the quantum predictions within the formalism of Von Neumann's projective measurement violate the proposition with a magnitude that grows exponentially with the number of particles. We have to give up either the existence of the directions or the formalism of Von Neumann's projective measurement. Therefore, Von Neumann's theory cannot depicture our physical world with a violation factor that grows exponentially with the number of particles. The theoretical formalism of the implementation of the Deutsch-Jozsa algorithm relies on Von Neumann's theory. We investigate whether Von Neumann's theory meets the Deutsch-Jozsa algorithm. We discuss the fact that the crucial contradiction makes the quantum-theoretical formulation of Deutsch-Jozsa algorithm questionable. Further, we discuss the fact that projective measurement theory does not meet an easy detector model for a single Pauli observable. Especially, we systematically describe our assertion based on more mathematical analysis using raw data. We propose a solution of the problem. Our solution is equivalent to changing Planck's constant ($\hbar$) to a new constant ($\hbar/\sqrt{2}$). It may be said that a new type of the quantum theory early approaches Newton's theory in the macroscopic scale than the old quantum theory does. We discuss how our solution is used in an implementation of Deutsch's algorithm.

•Mar 1, 2014•0 citations
Quantum superposition says that any physical system simultaneously exists in all of its possible states, the number of which is exponential in the number of entities composing the system. The strength of presence of each possible state in the superposition, i.e., its probability of being observed, is represented by its probability amplitude coefficient. The assumption that these coefficients must be represented physically disjointly from each other, i.e., localistically, is nearly universal in the quantum theory/computing literature. Alternatively, these coefficients can be represented using sparse distributed representations (SDR), wherein each coefficient is represented by small subset of an overall population of units, and the subsets can overlap. Specifically, I consider an SDR model in which the overall population consists of Q WTA clusters, each with K binary units. Each coefficient is represented by a set of Q units, one per cluster. Thus, K^Q coefficients can be represented with KQ units. Thus, the particular world state, X, whose coefficient's representation, R(X), is the set of Q units active at time t has the max probability and the probability of every other state, Y_i, at time t, is measured by R(Y_i)'s intersection with R(X). Thus, R(X) simultaneously represents both the particular state, X, and the probability distribution over all states. Thus, set intersection may be used to classically implement quantum superposition. If algorithms exist for which the time it takes to store (learn) new representations and to find the closest-matching stored representation (probabilistic inference) remains constant as additional representations are stored, this meets the criterion of quantum computing. Such an algorithm has already been described: it achieves this "quantum speed-up" without esoteric hardware, and in fact, on a single-processor, classical (Von Neumann) computer.
As early as 1982 Richard P. Feynman suggested that it might be impossible to simulate quantum mechanical phenomena with a computer without an exponential slowdown the efficiency of computation. He also proposed that this problem may be avoided by allowing the computer to run according to the laws of quantum mechanics, thus implicitely suggesting that a computer based on the quantum mechanical systems, a quantum computer, might have exponentially more computational efficiency than any classical one. A quantum mechanical phenomenon that never occurs classical physics and which actually makes quantum computation interesting and powerful, is the superposition of states, which, loosely speaking, means that instead of being totally one single state, a particle can be in between many states. Compare this to the elements of classical computer, bits. A bit takes values zero or one, but never anything between. In a quantum computer, one is able to store it both values simultaneously one quantum bit, equally weighted or not. Moreover, the classical computer one can store a number from zero to 2n−12^n-12n−1 a register of length nnn, whereas, quantum computation, all the values could be stored simultaneously. The computation, which is performed via unitary transformations the state vector space, then applies to all these values simultaneously. Thus the power of the quantum computation lies not the absolute speed of the hypothetetical quantum computer but the possibility to actually follow many computational path simultaneously, as a nondeterministic automaton does. Alas, the observation of the outcome will yield only one value destroying the rest irreversibly. However, using a procedure smart enough one could obtain some valuable information about the computation.
The superposition state of qubits in quantum computers enables a more efficient data representation than conventional binary methods in classical computers. Grover’s algorithm amplifies the amplitude of a target state within a superposed set of states having equal amplitudes. However, except for a 2-qubit system, the amplitudes of the nontarget states and left residual amplitudes induced by the algorithm do not reduce to zero. Therefore, a new method was devised to overcome this drawback. We select new target state among the nontarget states by applying Grover’s algorithm and obtain two distinct states with different amplitudes. Consequently, by excluding duplicate cases, this method enables the representation of [Formula: see text] data points. This technique is referred to as superdense data representation (SDR). Specifically, SDR is a new data representation method for quantum computers using superposition and entanglement. This offers several advantages for encoding data. For instance, 8-qubit data can be effectively represented in 4-qubit, thereby reducing the resources required to store the information. Additionally, SDR allows the representation of more complex data, such as Unicode, without increasing calculation or storage costs. UTF-8 encoding method can be implemented using only eight qubits. By extending SDR, Asian languages that require more than two bytes of data can also be expressed using eight qubits.
Four myths about quantum computingThis chapter relies on a bit of quantum physics jargon.See the chapter 'An introduction to the quantum world' for a quick introduction. Myth 1: Quantum computers find all solutions at onceThis myth is likely the most technical, and builds on a misinterpretation of the concept of superposition.A single qubit can be in two states at the same time (0 and 1), two qubits can represent four states (00, 01, 10, 11), and three qubits are potentially in eight unique configurations simultaneously.As we increase the number of qubits, this number of coexisting states scales exponentially!This means that a mere 1000 qubits can effectively 'store' 2 1000 unique values, all at the same time.That's an incomprehensibly large number, much more than there are atoms in the visible universe.Even the fastest computers in the world couldn't loop through all these states in a lifetime.Each of these states can be interpreted like a file on a computer, be it an Excel spreadsheet, a web page, a CAD drawing, or whatever kind of data we choose to work with.A smart computer scientist can also devise a way to make 1000 bits represent 'solutions' to a problem.For example, imagine that we want to find an optimal aeroplane wing that generates incredible lift while requiring as few materials as possible.Using quantum superposition, we might represent 2 1000 such wings simultaneously.We picked the example of aeroplane wings because simulating their aerodynamic properties requires a pretty hefty computation.Let's assume that we have written such a computer program that accurately simulates any wing.Let's call that program f .It will output 1 if the wing works well (according to whatever metric), and 0 otherwise.Surely, the program takes a very large number of computation steps, which we'll call T. The program will need some input, denoted by x , which is a 1000-bit description of all the relevant properties of a hypothetical aeroplane wing.In other words, the computer program computes f (x) = 1 if x is a fantastic wing, and f (x) = 0 if it's rubbish.Now, a quantum computer should be able to execute any classical function, right?We should be able to run f on a quantum computer, but now we have the unique feature that the 1000-qubit input can represent a humongous number of potential aeroplane wings at the same time.By doing a mere T computational steps, we can check the properties of 2 1000 solutions!
If the bits of computers are someday scaled down to the size of individual atoms, quantum mechanical effects may profoundly change the nature of computation itself. The wave function of such a quantum computer could consist of a superposition of many computations carried out simultaneously; this kind of parallelism could be exploited to make some important computational problems, like the prime factoring of large integers, tractable. However, building such a quantum computer would place undreamed of demands on the experimental realization of highly quantum-coherent systems; present-day experimental capabilities in atomic physics and other fields permit only the most rudimentary implementation of quantum computation.
We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained for quantum circuits which---without the additional sparsity promise---are considered hard to simulate. Our results apply in particular to a family of Fourier sampling circuits (which have structural similarities to Shor's factoring algorithm) but also to several other circuit families, such as IQP circuits. Our results provide examples of quantum circuits that cannot achieve exponential speed-ups due to the presence of too much destructive interference i.e. too many cancelations of amplitudes. The crux of our classical simulation is an efficient algorithm for approximating the significant Fourier coefficients of a class of states called computationally tractable states. The latter result may have applications beyond the scope of this work. In the proof we employ and extend sparse approximation techniques, in particular the Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.
We discuss the fact that there is a crucial contradiction within Von Neumann's theory. We derive a proposition concerning a quantum expected value under an assumption of the existence of the orientation of reference frames in NNN spin-1/2 systems (1≤N<+∞1 \leq N < +\infty1≤N<+∞). This assumption intuitively depictures our physical world. However, the quantum predictions within the formalism of Von Neumann's projective measurement violate the proposition with a magnitude that grows exponentially with the number of particles. We have to give up either the existence of the directions or the formalism of Von Neumann's projective measurement. Therefore, Von Neumann's theory cannot depicture our physical world with a violation factor that grows exponentially with the number of particles. The theoretical formalism of the implementation of the Deutsch-Jozsa algorithm relies on Von Neumann's theory. We investigate whether Von Neumann's theory meets the Deutsch-Jozsa algorithm. We discuss the fact that the crucial contradiction makes the quantum-theoretical formulation of Deutsch-Jozsa algorithm questionable. Further, we discuss the fact that projective measurement theory does not meet an easy detector model for a single Pauli observable. Especially, we systematically describe our assertion based on more mathematical analysis using raw data. We propose a solution of the problem. Our solution is equivalent to changing Planck's constant (ℏ\hbarℏ) to a new constant (ℏ/2\hbar/\sqrt{2}ℏ/2​). It may be said that a new type of the quantum theory early approaches Newton's theory in the macroscopic scale than the old quantum theory does. We discuss how our solution is used in an implementation of Deutsch's algorithm.