The possibility of building a quantum computer is critically analyzed. The main point is that the general state of the hypothetical quantum computer with N qubits is characterized by 2N quantum amplitudes, which are complex numbers restricted by the normalization condition only. It looks highly improbable that it will ever be possible to keep under our control this number of complex parameters even for modest values of [Formula: see text] 50 or 100.
The possibility of building a quantum computer is critically analyzed. The main point is that the general state of the hypothetical quantum computer with N qubits is characterized by 2N quantum amplitudes, which are complex numbers restricted by the normalization condition only. It looks highly improbable that it will ever be possible to keep under our control this number of complex parameters even for modest values of [Formula: see text] 50 or 100.
In the hypothetical quantum computing one replaces the classical twostate bit by a quantum element (qubit) with two basic states, ↑ and ↓.Its arbitrary state is described by the wave function ψ = a↑+ b↓, where a and b are complex amplitudes, satisfying the normalization condition.Unlike the classical bit, that can be only in one of the two states, ↑ or ↓, the qubit can be in a continuum of states defined by the quantum amplitudes a and b.The qubit is a continuous object.At a given moment, the state of a quantum computer with N qubits is characterized by 2 N quantum amplitudes, which are continuous variables restricted by the normalization condition only.Thus, the hypothetical quantum computer is an analog machine characterized by a super-astronomical number of continuous variables (even for N~100÷1000).Their values cannot be arbitrary, they must be under our control.Thus the answer to the question in title is: When physicists and engineers will learn to keep under control this number of continuous parameters, which means -never.
The quantum computer is supposed to process information by applying unitary transformations to 2 N complex amplitudes defining the state of N qubits. A useful machine needing N~10 3 or more, the number of continuous parameters describing the state of a quantum computer at any given moment is at least 2 1000 ~10 300 which is much greater than the number of protons in the Universe. However, the theorists believe that the feasibility of large-scale quantum computing has been proved via the “threshold theorem”. Like for any theorem, the proof is based on a number of assumptions considered as axioms. However, in the physical world none of these assumptions can be fulfilled exactly. Any assumption can be only approached with some limited precision. So, the rather meaningless “error per qubit per gate” threshold must be supplemented by a list of the precisions with which all assumptions behind the threshold theorem should hold. Such a list still does not exist. The theory also seems to ignore the undesired free evolution of the quantum computer caused by the energy differences of quantum states entering any given superposition. Another important point is that the hypothetical quantum computer will be a system of 10 3 –10 6 qubits PLUS an extremely complex and monstrously sophisticated classical apparatus. This huge and strongly nonlinear system will generally exhibit instabilities and chaotic behavior.
An intense effort is being made today to build a quantum computer. Instead of presenting what has been achieved, I invoke analogies from the history of science in an attempt to glimpse what the future might hold. Quantum computing is possible in principle—there are no known laws of Nature that prevent it—yet scaling up the few qubits demonstrated so far has proven to be exceedingly difficult. While this could be regarded merely as a technological or practical impediment, I argue that this difficulty might be a symptom of new laws of physics waiting to be discovered. I distinguish between ‘‘strong’’ and ‘‘weak’’ emergentist positions. The former assumes that a critical value of a parameter exists (one that is most likely related to the complexity of the states involved) at which the quantum-mechanical description breaks down, in other words, that quantum mechanics will turn out to be an incomplete description of reality. The latter assumes that quantum mechanics will remain as a universally valid theory, but that the classical resources required to build a real quantum computer scale up with the number of qubits, which hints that a limiting principle is at work.
Quantum computation is not an imminent achievement . We will not wake up tomorrow and find quantum computers on our desks. At the time of this writing, IBM has just unveiled the Condor – a chip containing 1,121 superconducting qubits. This number will likely increase (perhaps spectacularly) in the near future. However, the qubits have a relatively large error rate and, in the absence of a breakthrough advance that significantly lowers this rate, one would need hundreds of physical qubits to realize an error-corrected logical qubit. Predicting how long it will take to achieve the controlled manipulation of thousands of (logical) qubits (i.e., a number of qubits consistent with the “useful” implementation of known quantum algorithms) is probably not a rational undertaking, at least for a scientist. The most pessimistic experts regard the lively research activity in quantum computation as a waste of time and resources. But the pervading mood in this field is one of cautious optimism, particularly considering the possibility of achieving useful tasks (e.g., simulating quantum systems) with a sufficiently large number of “imperfect” qubits. Expediency may be responsible for some of this optimism; a good feeling about the prospects for quantum computation certainly helps when it comes to publishing papers and getting funded. Ultimately, however, the responsibility for the wise distribution of resources rests with the funding agencies; scientists, on the other hand, are called to explore every aspect of real and possible worlds that looks fascinating and worthy of their curiosity. From this perspective, quantum computation (defined broadly) offers plenty of opportunities for producing “good science.” The problems brought to the fore by the development of this field range from basic questions regarding the foundations of quantum mechanics and unsolved problems in computational complexity, to the investigation of new phases of matter (e.g., topological quantum phases), the quest for “complete” control over quantum systems, and the critical need for significant advances in materials science and device fabrication (e.g., engineering nanoscale heterostructures with atomic precision). Progress in these areas will naturally open new possibilities for interesting applications. Precisely identifying these applications is premature, but building a (general purpose) quantum computer will not necessarily be among the first of them.
Quantum algorithms claim significant speedup over their classical counterparts for solving many problems. An important aspect of many of these algorithms is the existence of a quantum oracle, which needs to be implemented efficiently in order to realize the claimed advantages in practice. A quantum random access memory (QRAM) is a promising architecture for realizing these oracles. In this paper we develop a new design for QRAM and implement it with Clifford+T circuit. We focus on optimizing the T-count and T-depth since non-Clifford gates are the most expensive to implement fault-tolerantly in most error correction schemes. Integral to our design is a polynomial encoding of bit strings and so we refer to this design as [Formula: see text]. Compared to the previous state-of-the-art bucket brigade architecture for QRAM, we achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit-count same. Specifically, if N is the number of memory locations to be queried, then [Formula: see text] has T-depth [Formula: see text], T-count [Formula: see text] and uses O(N) logical qubits, while the bucket brigade circuit has T-depth [Formula: see text], T-count O(N) and uses O(N) qubits. Combining two [Formula: see text] we design a quantum look-up-table, [Formula: see text], that has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. A quantum look-up table (qLUT) or quantum read-only memory (QROM) has restricted functionality than a QRAM. For example, it cannot write into a memory location and the circuit needs to be compiled each time the contents of the memory change. The previous state-of-the-art CSWAP architecture has T-depth [Formula: see text], T-count [Formula: see text] and qubit count [Formula: see text]. Thus we achieve a double exponential improvement in T-depth while keeping the T-count and qubit-count asymptotically same. Additionally, with our polynomial encoding of bit strings, we develop a method to optimize the Toffoli-count of circuits, specially those consisting of multi-controlled-NOT gates.