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

Quantum computing does not have capability of physically implementing algorithm-output extraction: a nonconstructive proof for the nonexistence of the process solution T(t) satisfying the equivalence between bit-output probability and outcome probability

Bowen Liu

Published Feb 28, 2023• 0 citations
Publisher

Abstract

Abstract Quantum computing consists of algorithm and algorithm-output extraction. There are two major philosophical bubbles of quantum computing: the output-extraction model has low mathematical coverage closing to zero; the real mathematized goal of output-extraction, the existence of process solution, is hidden. Piercing the two bubbles, we reduce the mathematical structure of quantum computing to the two barest mathematical problems: to prove the existence of the program solution for given input and output state in algorithm; to prove the existence of process solution for given initial and final probability in output-extraction. The mathematical theme of algorithm-output extraction is two probability binaries (PA(λn), PB(λn) and (PB(λn), PBorn(λn)). For (PA(λn), PB(λn)), PA(λn) is the outcome probability obtained by the researchers by means of the eigenvalue-to-outcome transmission, PB(λn) is the probability within the state space based on the average of the results obtained from a finite discrete set of trials. The researchers assert PA(λn) = PB(λn), and assume that the mathematical basis for PA(λn) = PB(λn) is the existence of process solution satisfying PA(λn) = PB(λn). For (PB(λn), PBorn(λn), PBorn(λn) ≡|Ψ|2is the theoretical probability for single-bit output specified by quantum mechanical principles. The researchers assert PB(λn) = PBorn(λn), and assume that the mathematical basis for PB(λn) = PBorn(λn) is the so-called Law (QC) of Large Numbers. Thus, there are two major math-bugs of quantum computing: the existence of process solution satisfying PA(λn) = PB(λn) is unproven, the Law (QC) of Large Numbers guaranteeing PB(λn) = PBorn(λn) is unproven. For the first math-bug, we introduce a completely new proof method, nonconstructive proof based on path classification. We reformulate the problem of the existence of process solution as the existence problem of path classes. Physicists rarely have the opportunity to use non-constructive proofs, which are very effective for the desired existence problem. For our nonconstructive proof, it is not necessary to provide an example of a path and a mathematical algorithm that produces an example of the path. By means of non-constructive proof, we have shown the nonexistence of process solution satisfying PA(λn) = PB(λn). For the second math-bug, we show that the law (QC) of large numbers is not a corollary of any known law of large numbers in probability theory. For the qubit-output probability of quantum computing experiments there is no reliable basis of probability theory. We provide the three examples to prove that all known minimized quantum factorization experiments are invalid. We conclude that Quantum computing cannot survive the two major math-bugs. quantum computing theory is wrong because the mathematics of the output-extraction theory is wrong; the output-extraction theory, which assumes PA(λn) = PB(λn) = PBorn(λn), is wrong because PA(λn) = PB(λn) is wrong and PB(λn) = PBorn(λn) is unproven. Our study shows that two major math-bugs of quantum computing are very serious and unfixable, because they challenge mathematicians' understanding of the underlying mathematical rules.

DOI
10.21203/rs.3.rs-2621954/v1

Related papers

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

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•22 citations

Design Methods for Reliable Quantum Circuits

Alexandru Paler

Quantum computing is an emerging technology that has the potential to change the perspectives and applications of computing in general. A wide range of applications are enabled: from faster algorithmic solutions of classically still difficult problems to theoretically more secure communication protocols. A quantum computer uses the quantum mechanical effects of particles or particle-like systems, and a major similarity between quantum and classical computers consists of both being abstracted as information processing machines. Whereas a classical computer operates on classical digital information, the quantum computer processes quantum information, which shares similarities with analog signals. One of the central differences between the two types of information is that classical information is more fault-tolerant when compared to its quantum counterpart. Faults are the result of the quantum systems being interfered by external noise, but during the last decades quantum error correction codes (QECC) were proposed as methods to reduce the effect of noise. Reliable quantum circuits are the result of designing circuits that operate directly on encoded quantum information, but the circuit’s reliability is also increased by supplemental redundancies, such as sub-circuit repetitions. Reliable quantum circuits have not been widely used, and one of the major obstacles is their vast associated resource overhead, but recent quantum computing architectures show promising scalabilities. Consequently the number of particles used for computing can be more easily increased, and that the classical control hardware (inherent for quantum computation) is also more reliable. Reliable quantum circuits haev been investigated for almost as long as general quantum computing, but their limited adoption (until recently) has not generated enough interest into their systematic design. The continuously increasing practical relevance of reliability motivates the present thesis to investigate some of the first answers to questions related to the background and the methods forming a reliable quantum circuit design stack. The specifics of quantum circuits are analysed from two perspectives: their probabilistic behaviour and their topological properties when a particular class of QECCs are used. The quantum phenomena, such as entanglement and superposition, are the computational resources used for designing quantum circuits. The discrete nature of classical information is missing for quantum information. An arbitrary quantum system can be in an infinite number of states, which are linear combinations of an exponential number of basis states. Any nontrivial linear combination of more than one basis states is called a state superposition. The effect of superpositions becomes evident when the state of the system is inferred (measured), as measurements are probabilistic with respect to their output: a nontrivial state superposition will collapse to one of the component basis states, and the measurement result is known exactly only after the measurement. A quantum system is, in general, composed from identical subsystems, meaning that a quantum computer (the complete system) operates on multiple similar particles (subsystems). Entanglement expresses the impossibility of separating the state of the subsystems from the state of the complete system: the nontrivial interactions between the subsystems result into a single indivisible state. Entanglement is an additional source of probabilistic behaviour: by measuring the state of a subsystem, the states of the unmeasured subsystems will probabilistically collapse to states from a well defined set of possible states. Superposition and entanglement are the building blocks of quantum information teleportation protocols, which in turn are used in state-of-the-art fault-tolerant quantum computing architectures. Information teleportation implies that the state of a subsystem is moved to a second subsystem without copying any information during the process. The probabilistic approach towards the design of quantum circuits is initiated by the extension of classical test and diagnosis methods. Quantum circuits are modelled similarly to classical circuits by defining gate-lists, and missing quantum gates are modelled by the single missing gate fault. The probabilistic approaches towards quantum circuits are facilitated by comparing these to stochastic circuits, which are a particular type of classical digital circuits. Stochastic circuits can be considered an emulation of analogue computing using digital components. A first proposed design method, based on the direct comparison, is the simulation of quantum circuits using stochastic circuits by mapping each quantum gate to a stochastic computing sub-circuit. The resulting stochastic circuit is compiled and simulated on FPGAs. The obtained results are encouraging and illustrate the capabilities of the proposed simulation technique. However, the exponential number of possible quantum basis states was translated into an exponential number of stochastic computing elements. A second contribution of the thesis is the proposal of test and diagnosis methods for both stochastic and quantum circuits. Existing verification (tomographic) methods of quantum circuits were targeting the reconstruction of the gate-lists. The repeated execution of the quantum circuit was followed by different but specific measurement at the circuit outputs. The similarities between stochastic and quantum circuits motivated the proposal of test and diagnosis methods that use a restricted set of measurement types, which minimise the number of circuit executions. The obtained simulation results show that the proposed validation methods improve the feasibility of quantum circuit tomography for small and medium size circuits. A third contribution of the thesis is the algorithmic formalisation of a problem encountered in teleportation-based quantum computing architectures. The teleportation results are probabilistic and require corrections represented as quantum gates from a particular set. However, there are known commutation properties of these gates with the gates used in the circuit. The corrections are not applied as dynamic gate insertions (during the circuit’s execution) into the gate-lists, but their effect is tracked through the circuit, and the corrections are applied only at circuit outputs. The simulation results show that the algorithmic solution is applicable for very large quantum circuits. Topological quantum computing (TQC) is based on a class of fault-tolerant quantum circuits that use the surface code as the underlying QECC. Quantum information is encoded in lattice-like structures and error protection is enabled by the topological properties of the lattice. The 3D structure of the lattice allows TQC computations to be visualised similarly to knot diagrams. Logical information is abstracted as strands and strand interactions (braids) represent logical quantum gates. Therefore, TQC circuits are abstracted using a geometrical description, which allows circuit input-output transformations (correlations) to be represented as geometric sub-structures. TQC design methods were not investigated prior to this work, and the thesis introduces the topological computational model by first analysing the necessary concepts. The proposed TQC design stack follows a top-down approach: an arbitrary quantum circuit is decomposed into the TQC supported gate set; the resulting circuit is mapped to a lattice of appropriate dimensions; relevant resulting topological properties are extracted and expressed using graphs and Boolean formulas. Both circuit representations are novel and applicable to TQC circuit synthesis and validation. Moreover, the Boolean formalism is broadened into a formal mechanism for proving circuit correctness. The thesis introduces TQC circuit synthesis, which is based on a novel logical gate geometric description, whose formal correctness is demonstrated. Two synthesis methods are designed, and both use a general planar representation of the circuit. Initial simulation results demonstrate the practicality and performance of the methods. An additional group of proposed design methods solves the problem of automatic correlation construction. The methods use validity criteria which were introduced and analysed beforehand in the thesis. Input-output correlations existing in the circuit are inferred using both the graph and the Boolean representation. The thesis extends the TQC state-of-the-art by recognising the importance of correlations in the validation process: correlation construction is used as a sub-routine for TQC circuit validation. The presented cross-layer validation procedure is useful when investigating both the QECC and the circuit, while a second proposed method is QECC-independent. Both methods are scalable and applicable even to very large circuits. The thesis completes with the analysis of TQC circuit identities, where the developed Boolean formalism is used. The proofs of former known circuit identities were either missing or complex, and the presented approach reduces the length of the proofs and represents a first step towards standardising them. A new identity is developed and detailed during the process of illustrating the known circuit identities. Reliable quantum circuits are a necessity for quantum computing to become reality, and specialised design methods are required to support the quest for scalable quantum computers. This thesis used a twofold approach towards this target: firstly by focusing on the probabilistic behaviour of quantum circuits, and secondly by considering the requirements of a promising quantum computing architecture, namely TQC. Both approaches resulted in a set of design methods enabling the investigation of reliable quantum circuits. The thesis contributes with the proposal of a new quantum simulation technique, no

•Jan 1, 2015•2 citations

Quantum computing is incompatible with Born Rule and the related measurement postulates, the qubit reading capability is falsified experimentally, and the Feynman-Deutsch quantum computing theory is low-strict, low-testable and infeasible.

Bowen Liu

Abstract (1) Deutsch stated: it is shown that quantum theory and the ‘universal quantum computer’ are compatible with the principle, that is, it is shown the compatibility of quantum computing with quantum mechanics. Born Rule and Time Evolution Postulate are the important ingredients of quantum theory. Deutsch et al. did not provide a proof of the compatibility of quantum computing with Born Rule (and Time Evolution Postulate), avoided the extraction of unitary transformation results in their papers, and defaulted that the output probability density can map to the observation-space CS C and to be read. We attribute the proof of the incompatibility of quantum computing with quantum mechanics to the proof of the incompatibility of quantum computing with Born Rule. The basic form of Born Rule is that \({\left| \psi \right|^2}\) represents the probability density for particles; if the system is in a state \(\left| \psi \right\rangle\), then the probability that the eigenvalue λ i of Q is found when Q is measured is P(λ i ) =\({\left| {\left\langle {{\lambda _n}} \right|\left. \psi \right\rangle } \right|^2}\). We show that in the technical scheme of quantum computing, there is an imposed strong constraint on Born Rule, that is, double \({\left| \psi \right|^2}\) hypothesis (i.e., Feynman-Deutsch’s \({\left| \psi \right|^2}\)(double) reading hypothesis), which requires that there is such a mapping from the state-space CS M to the observation-space CS C : \({\left| {{\psi _M}} \right|^2}\)→\({\left| {{\psi _C}} \right|^2}\), where \({\left| {{\psi _M}} \right|^2}\)is the probability density of the wavefunction \({\text{a}}\left| 0 \right\rangle +b\left| 1 \right\rangle\) of the single-qubit, \({\left| {{\psi _C}} \right|^2}\) is the probability density of the corresponding outcomes within CS C , and \({\left| {{\psi _C}} \right|^2}\) is equivalent to \({\left| {{\psi _M}} \right|^2}\). The original Born Rule does not assert the mapping \({\left| {{\psi _M}} \right|^2}\)→\({\left| {{\psi _C}} \right|^2}\). We demonstrate that in the technical scheme of quantum computing it is assumed that the single-qubit carrier-symbol snapshot traceability is the basis for the realization of the double \({\left| \psi \right|^2}\). We, using the Stern-Gerlach experiment and the chip engineer's contraction mapping experiment, experimentally falsify the single-qubit carrier-symbol snapshot traceability, and thus experimentally falsify the Feynman-Deutsch’s \({\left| \psi \right|^2}\)(double) reading hypothesis. In this way, we show that quantum computing is incompatible with Born Rule and the related measurement postulates, and the Feynman-Deutsch quantum computing theory is not feasible. The principal error of the Feynman-Deutsch theory is the mapping \({\left| {{\psi _M}} \right|^2}\)→\({\left| {{\psi _C}} \right|^2}\); the root of all errors in quantum computing is the double probability density hidden in the technical scheme, which is the false Born Rule. (2) The Feynman-Deutsch theory is a low-strict, low-testable and non-transparent theory for the following reasons: postulate-level assumptions are hidden in the technical scheme; the testability (falsifiability) of various parts of quantum computing has never been publicized. It has long been believed that quantum computing centers on unitary transformation sequence. We show that qubit reading is the only falsifiable part of quantum computing. Because falsifiable issue takes precedence over unfalsifiable issue, and principle-level issue takes precedence over non-principle-level issue, the priority of quantum computing research is the inapplicability of Born Rule to quantum computing rather than the applicability of unitary transformation. i.e., the real heart of quantum computing is the existence of \({\left| \psi \right|^2}\) mapping from CS M to CS C . We prove the fact that although algorithm and the algorithm’s output within CS M are carried out in the name of quantum technology, the "double \({\left| \psi \right|^2}\)" is actually independent of Born Rule, and independent of quantum mechanics. The methodological error of the Feynman-Deutsch theory is to exclude the inapplicability of Born Rule from the research field. (3) We re-examined the effectiveness of three published quantum computing (Shor factoring) experiments, and show that they are invalid in the sense of falsifiability criterion and the traversal criterion. The high risk of the infeasibility of quantum computing is completely underestimated. (4) In the last sections, we examine a topic with a higher degree of generality: the traceability (direction non-constraint) of single-particle information process. Using the “reproducible effect” method suggested by Popper, we show that the realization of quantum computing violates human's existing knowledge about the contraction mapping experiments of two spaces. The proofs in this paper show that the compression mapping experiment in meso-micro scale and the physical version of Gödel's incompleteness theorem are more profound principles of quantum physics (including Born Rule and the related measurement postulates).

•Apr 4, 2022•0 citations

Quantum Algorithms

A. O. Pittenger

We are now ready to assemble quantum subroutines into quantum algorithms. A reasonable first question is: Are there problems which can be solved efficiently on a quantum computer? In his analysis of a universal quantum computer [25], Deutsch illustrated quantum parallelism by constructing a procedure to compute the parity f (0) ⊕ f (1) of a function on one bit. In a generalization of this context, Deutsch and Jozsa [27] defined a quantum algorithm that could solve a problem more efficiently than is possible on a classical computer. This problem helped motivate the search for algorithms that could solve “real” problems, and Simon [67] provided an example that inspired Shor’s subsequent work on the factoring problem and on the discrete logarithm problem. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Birkhäuser Boston eBooks•Jan 1, 2001•0 citations

From Necessary Conditions to Binary Observation: A Working Hypothesis for a 3–8–2 Hierarchical Generative Framework

王有福

This paper proposes an exploratory “3–8–2” hierarchical generative framework designed to distinguish three different logical layers: a necessary-condition layer, a generative-process layer, and an observational-output layer. The current working hypothesis is: 3\ \text{necessary conditions}\rightarrow8\ \text{candidate generative processes}\rightarrow2\ \text{binary observational outcomes}. At the first layer, “Yuan” is provisionally defined as the minimal closed condition structure formed by three mutually irreducible and jointly necessary conditions. The number 3 therefore refers to the number of necessary conditions rather than to a number of physical states. At the second layer, the number 8 refers to eight candidate generative processes, process configurations, or generative pathways that may emerge once the necessary conditions are satisfied. Their precise mathematical origin and physical interpretation remain open. In particular, this framework does not assume that these eight processes correspond to an established eight-state quantum ontology. At the third layer, the number 2 refers to binary observational outcomes, represented as 0/1, obtained through coarse-graining, projection, or limited observational resolution. These binary outputs are therefore treated as observational results rather than as evidence that the underlying ontology is fundamentally binary. The aim of this work is not to claim a new physical ontology, but to formulate a testable hierarchical research framework that clearly separates the conditions required for a process to exist, the mechanisms through which structures or processes are generated, and the outcomes accessible to observation. The central open problem is to identify the three irreducible necessary conditions that constitute “Yuan” and to determine whether the minimum number of such conditions is genuinely three rather than two, four, or more. At its present stage, the proposed framework should be regarded as a working hypothesis and structural research program. Its possible connections to quantum processes, hidden structures, and physical realizations remain open and unproven.

•Sep 2, 2026•0 citations
Abstract Quantum computing consists of algorithm and algorithm-output extraction. There are two major philosophical bubbles of quantum computing: the output-extraction model has low mathematical coverage closing to zero; the real mathematized goal of output-extraction, the existence of process solution, is hidden. Piercing the two bubbles, we reduce the mathematical structure of quantum computing to the two barest mathematical problems: to prove the existence of the program solution for given input and output state in algorithm; to prove the existence of process solution for given initial and final probability in output-extraction. The mathematical theme of algorithm-output extraction is two probability binaries (PA(λn), PB(λn) and (PB(λn), PBorn(λn)). For (PA(λn), PB(λn)), PA(λn) is the outcome probability obtained by the researchers by means of the eigenvalue-to-outcome transmission, PB(λn) is the probability within the state space based on the average of the results obtained from a finite discrete set of trials. The researchers assert PA(λn) = PB(λn), and assume that the mathematical basis for PA(λn) = PB(λn) is the existence of process solution satisfying PA(λn) = PB(λn). For (PB(λn), PBorn(λn), PBorn(λn) ≡|Ψ|2is the theoretical probability for single-bit output specified by quantum mechanical principles. The researchers assert PB(λn) = PBorn(λn), and assume that the mathematical basis for PB(λn) = PBorn(λn) is the so-called Law (QC) of Large Numbers. Thus, there are two major math-bugs of quantum computing: the existence of process solution satisfying PA(λn) = PB(λn) is unproven, the Law (QC) of Large Numbers guaranteeing PB(λn) = PBorn(λn) is unproven. For the first math-bug, we introduce a completely new proof method, nonconstructive proof based on path classification. We reformulate the problem of the existence of process solution as the existence problem of path classes. Physicists rarely have the opportunity to use non-constructive proofs, which are very effective for the desired existence problem. For our nonconstructive proof, it is not necessary to provide an example of a path and a mathematical algorithm that produces an example of the path. By means of non-constructive proof, we have shown the nonexistence of process solution satisfying PA(λn) = PB(λn). For the second math-bug, we show that the law (QC) of large numbers is not a corollary of any known law of large numbers in probability theory. For the qubit-output probability of quantum computing experiments there is no reliable basis of probability theory. We provide the three examples to prove that all known minimized quantum factorization experiments are invalid. We conclude that Quantum computing cannot survive the two major math-bugs. quantum computing theory is wrong because the mathematics of the output-extraction theory is wrong; the output-extraction theory, which assumes PA(λn) = PB(λn) = PBorn(λn), is wrong because PA(λn) = PB(λn) is wrong and PB(λn) = PBorn(λn) is unproven. Our study shows that two major math-bugs of quantum computing are very serious and unfixable, because they challenge mathematicians' understanding of the underlying mathematical rules.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
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 computing is an emerging technology that has the potential to change the perspectives and applications of computing in general. A wide range of applications are enabled: from faster algorithmic solutions of classically still difficult problems to theoretically more secure communication protocols. A quantum computer uses the quantum mechanical effects of particles or particle-like systems, and a major similarity between quantum and classical computers consists of both being abstracted as information processing machines. Whereas a classical computer operates on classical digital information, the quantum computer processes quantum information, which shares similarities with analog signals. One of the central differences between the two types of information is that classical information is more fault-tolerant when compared to its quantum counterpart. Faults are the result of the quantum systems being interfered by external noise, but during the last decades quantum error correction codes (QECC) were proposed as methods to reduce the effect of noise. Reliable quantum circuits are the result of designing circuits that operate directly on encoded quantum information, but the circuit’s reliability is also increased by supplemental redundancies, such as sub-circuit repetitions. Reliable quantum circuits have not been widely used, and one of the major obstacles is their vast associated resource overhead, but recent quantum computing architectures show promising scalabilities. Consequently the number of particles used for computing can be more easily increased, and that the classical control hardware (inherent for quantum computation) is also more reliable. Reliable quantum circuits haev been investigated for almost as long as general quantum computing, but their limited adoption (until recently) has not generated enough interest into their systematic design. The continuously increasing practical relevance of reliability motivates the present thesis to investigate some of the first answers to questions related to the background and the methods forming a reliable quantum circuit design stack. The specifics of quantum circuits are analysed from two perspectives: their probabilistic behaviour and their topological properties when a particular class of QECCs are used. The quantum phenomena, such as entanglement and superposition, are the computational resources used for designing quantum circuits. The discrete nature of classical information is missing for quantum information. An arbitrary quantum system can be in an infinite number of states, which are linear combinations of an exponential number of basis states. Any nontrivial linear combination of more than one basis states is called a state superposition. The effect of superpositions becomes evident when the state of the system is inferred (measured), as measurements are probabilistic with respect to their output: a nontrivial state superposition will collapse to one of the component basis states, and the measurement result is known exactly only after the measurement. A quantum system is, in general, composed from identical subsystems, meaning that a quantum computer (the complete system) operates on multiple similar particles (subsystems). Entanglement expresses the impossibility of separating the state of the subsystems from the state of the complete system: the nontrivial interactions between the subsystems result into a single indivisible state. Entanglement is an additional source of probabilistic behaviour: by measuring the state of a subsystem, the states of the unmeasured subsystems will probabilistically collapse to states from a well defined set of possible states. Superposition and entanglement are the building blocks of quantum information teleportation protocols, which in turn are used in state-of-the-art fault-tolerant quantum computing architectures. Information teleportation implies that the state of a subsystem is moved to a second subsystem without copying any information during the process. The probabilistic approach towards the design of quantum circuits is initiated by the extension of classical test and diagnosis methods. Quantum circuits are modelled similarly to classical circuits by defining gate-lists, and missing quantum gates are modelled by the single missing gate fault. The probabilistic approaches towards quantum circuits are facilitated by comparing these to stochastic circuits, which are a particular type of classical digital circuits. Stochastic circuits can be considered an emulation of analogue computing using digital components. A first proposed design method, based on the direct comparison, is the simulation of quantum circuits using stochastic circuits by mapping each quantum gate to a stochastic computing sub-circuit. The resulting stochastic circuit is compiled and simulated on FPGAs. The obtained results are encouraging and illustrate the capabilities of the proposed simulation technique. However, the exponential number of possible quantum basis states was translated into an exponential number of stochastic computing elements. A second contribution of the thesis is the proposal of test and diagnosis methods for both stochastic and quantum circuits. Existing verification (tomographic) methods of quantum circuits were targeting the reconstruction of the gate-lists. The repeated execution of the quantum circuit was followed by different but specific measurement at the circuit outputs. The similarities between stochastic and quantum circuits motivated the proposal of test and diagnosis methods that use a restricted set of measurement types, which minimise the number of circuit executions. The obtained simulation results show that the proposed validation methods improve the feasibility of quantum circuit tomography for small and medium size circuits. A third contribution of the thesis is the algorithmic formalisation of a problem encountered in teleportation-based quantum computing architectures. The teleportation results are probabilistic and require corrections represented as quantum gates from a particular set. However, there are known commutation properties of these gates with the gates used in the circuit. The corrections are not applied as dynamic gate insertions (during the circuit’s execution) into the gate-lists, but their effect is tracked through the circuit, and the corrections are applied only at circuit outputs. The simulation results show that the algorithmic solution is applicable for very large quantum circuits. Topological quantum computing (TQC) is based on a class of fault-tolerant quantum circuits that use the surface code as the underlying QECC. Quantum information is encoded in lattice-like structures and error protection is enabled by the topological properties of the lattice. The 3D structure of the lattice allows TQC computations to be visualised similarly to knot diagrams. Logical information is abstracted as strands and strand interactions (braids) represent logical quantum gates. Therefore, TQC circuits are abstracted using a geometrical description, which allows circuit input-output transformations (correlations) to be represented as geometric sub-structures. TQC design methods were not investigated prior to this work, and the thesis introduces the topological computational model by first analysing the necessary concepts. The proposed TQC design stack follows a top-down approach: an arbitrary quantum circuit is decomposed into the TQC supported gate set; the resulting circuit is mapped to a lattice of appropriate dimensions; relevant resulting topological properties are extracted and expressed using graphs and Boolean formulas. Both circuit representations are novel and applicable to TQC circuit synthesis and validation. Moreover, the Boolean formalism is broadened into a formal mechanism for proving circuit correctness. The thesis introduces TQC circuit synthesis, which is based on a novel logical gate geometric description, whose formal correctness is demonstrated. Two synthesis methods are designed, and both use a general planar representation of the circuit. Initial simulation results demonstrate the practicality and performance of the methods. An additional group of proposed design methods solves the problem of automatic correlation construction. The methods use validity criteria which were introduced and analysed beforehand in the thesis. Input-output correlations existing in the circuit are inferred using both the graph and the Boolean representation. The thesis extends the TQC state-of-the-art by recognising the importance of correlations in the validation process: correlation construction is used as a sub-routine for TQC circuit validation. The presented cross-layer validation procedure is useful when investigating both the QECC and the circuit, while a second proposed method is QECC-independent. Both methods are scalable and applicable even to very large circuits. The thesis completes with the analysis of TQC circuit identities, where the developed Boolean formalism is used. The proofs of former known circuit identities were either missing or complex, and the presented approach reduces the length of the proofs and represents a first step towards standardising them. A new identity is developed and detailed during the process of illustrating the known circuit identities. Reliable quantum circuits are a necessity for quantum computing to become reality, and specialised design methods are required to support the quest for scalable quantum computers. This thesis used a twofold approach towards this target: firstly by focusing on the probabilistic behaviour of quantum circuits, and secondly by considering the requirements of a promising quantum computing architecture, namely TQC. Both approaches resulted in a set of design methods enabling the investigation of reliable quantum circuits. The thesis contributes with the proposal of a new quantum simulation technique, no
Abstract (1) Deutsch stated: it is shown that quantum theory and the ‘universal quantum computer’ are compatible with the principle, that is, it is shown the compatibility of quantum computing with quantum mechanics. Born Rule and Time Evolution Postulate are the important ingredients of quantum theory. Deutsch et al. did not provide a proof of the compatibility of quantum computing with Born Rule (and Time Evolution Postulate), avoided the extraction of unitary transformation results in their papers, and defaulted that the output probability density can map to the observation-space CS C and to be read. We attribute the proof of the incompatibility of quantum computing with quantum mechanics to the proof of the incompatibility of quantum computing with Born Rule. The basic form of Born Rule is that ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2 represents the probability density for particles; if the system is in a state ∣ψ⟩\left| \psi \right\rangle∣ψ⟩, then the probability that the eigenvalue λ i of Q is found when Q is measured is P(λ i ) =∣⟨λn∣ψ⟩∣2{\left| {\left\langle {{\lambda _n}} \right|\left. \psi \right\rangle } \right|^2}∣⟨λn​∣ψ⟩∣2. We show that in the technical scheme of quantum computing, there is an imposed strong constraint on Born Rule, that is, double ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2 hypothesis (i.e., Feynman-Deutsch’s ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2(double) reading hypothesis), which requires that there is such a mapping from the state-space CS M to the observation-space CS C : ∣ψM∣2{\left| {{\psi _M}} \right|^2}∣ψM​∣2→∣ψC∣2{\left| {{\psi _C}} \right|^2}∣ψC​∣2, where ∣ψM∣2{\left| {{\psi _M}} \right|^2}∣ψM​∣2is the probability density of the wavefunction a∣0⟩+b∣1⟩{\text{a}}\left| 0 \right\rangle +b\left| 1 \right\ranglea∣0⟩+b∣1⟩ of the single-qubit, ∣ψC∣2{\left| {{\psi _C}} \right|^2}∣ψC​∣2 is the probability density of the corresponding outcomes within CS C , and ∣ψC∣2{\left| {{\psi _C}} \right|^2}∣ψC​∣2 is equivalent to ∣ψM∣2{\left| {{\psi _M}} \right|^2}∣ψM​∣2. The original Born Rule does not assert the mapping ∣ψM∣2{\left| {{\psi _M}} \right|^2}∣ψM​∣2→∣ψC∣2{\left| {{\psi _C}} \right|^2}∣ψC​∣2. We demonstrate that in the technical scheme of quantum computing it is assumed that the single-qubit carrier-symbol snapshot traceability is the basis for the realization of the double ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2. We, using the Stern-Gerlach experiment and the chip engineer's contraction mapping experiment, experimentally falsify the single-qubit carrier-symbol snapshot traceability, and thus experimentally falsify the Feynman-Deutsch’s ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2(double) reading hypothesis. In this way, we show that quantum computing is incompatible with Born Rule and the related measurement postulates, and the Feynman-Deutsch quantum computing theory is not feasible. The principal error of the Feynman-Deutsch theory is the mapping ∣ψM∣2{\left| {{\psi _M}} \right|^2}∣ψM​∣2→∣ψC∣2{\left| {{\psi _C}} \right|^2}∣ψC​∣2; the root of all errors in quantum computing is the double probability density hidden in the technical scheme, which is the false Born Rule. (2) The Feynman-Deutsch theory is a low-strict, low-testable and non-transparent theory for the following reasons: postulate-level assumptions are hidden in the technical scheme; the testability (falsifiability) of various parts of quantum computing has never been publicized. It has long been believed that quantum computing centers on unitary transformation sequence. We show that qubit reading is the only falsifiable part of quantum computing. Because falsifiable issue takes precedence over unfalsifiable issue, and principle-level issue takes precedence over non-principle-level issue, the priority of quantum computing research is the inapplicability of Born Rule to quantum computing rather than the applicability of unitary transformation. i.e., the real heart of quantum computing is the existence of ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2 mapping from CS M to CS C . We prove the fact that although algorithm and the algorithm’s output within CS M are carried out in the name of quantum technology, the "double ∣ψ∣2{\left| \psi \right|^2}∣ψ∣2" is actually independent of Born Rule, and independent of quantum mechanics. The methodological error of the Feynman-Deutsch theory is to exclude the inapplicability of Born Rule from the research field. (3) We re-examined the effectiveness of three published quantum computing (Shor factoring) experiments, and show that they are invalid in the sense of falsifiability criterion and the traversal criterion. The high risk of the infeasibility of quantum computing is completely underestimated. (4) In the last sections, we examine a topic with a higher degree of generality: the traceability (direction non-constraint) of single-particle information process. Using the “reproducible effect” method suggested by Popper, we show that the realization of quantum computing violates human's existing knowledge about the contraction mapping experiments of two spaces. The proofs in this paper show that the compression mapping experiment in meso-micro scale and the physical version of Gödel's incompleteness theorem are more profound principles of quantum physics (including Born Rule and the related measurement postulates).
We are now ready to assemble quantum subroutines into quantum algorithms. A reasonable first question is: Are there problems which can be solved efficiently on a quantum computer? In his analysis of a universal quantum computer [25], Deutsch illustrated quantum parallelism by constructing a procedure to compute the parity f (0) ⊕ f (1) of a function on one bit. In a generalization of this context, Deutsch and Jozsa [27] defined a quantum algorithm that could solve a problem more efficiently than is possible on a classical computer. This problem helped motivate the search for algorithms that could solve “real” problems, and Simon [67] provided an example that inspired Shor’s subsequent work on the factoring problem and on the discrete logarithm problem. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This paper proposes an exploratory “3–8–2” hierarchical generative framework designed to distinguish three different logical layers: a necessary-condition layer, a generative-process layer, and an observational-output layer. The current working hypothesis is: 3\ \text{necessary conditions}\rightarrow8\ \text{candidate generative processes}\rightarrow2\ \text{binary observational outcomes}. At the first layer, “Yuan” is provisionally defined as the minimal closed condition structure formed by three mutually irreducible and jointly necessary conditions. The number 3 therefore refers to the number of necessary conditions rather than to a number of physical states. At the second layer, the number 8 refers to eight candidate generative processes, process configurations, or generative pathways that may emerge once the necessary conditions are satisfied. Their precise mathematical origin and physical interpretation remain open. In particular, this framework does not assume that these eight processes correspond to an established eight-state quantum ontology. At the third layer, the number 2 refers to binary observational outcomes, represented as 0/1, obtained through coarse-graining, projection, or limited observational resolution. These binary outputs are therefore treated as observational results rather than as evidence that the underlying ontology is fundamentally binary. The aim of this work is not to claim a new physical ontology, but to formulate a testable hierarchical research framework that clearly separates the conditions required for a process to exist, the mechanisms through which structures or processes are generated, and the outcomes accessible to observation. The central open problem is to identify the three irreducible necessary conditions that constitute “Yuan” and to determine whether the minimum number of such conditions is genuinely three rather than two, four, or more. At its present stage, the proposed framework should be regarded as a working hypothesis and structural research program. Its possible connections to quantum processes, hidden structures, and physical realizations remain open and unproven.