The circuit model of quantum computation is reformulated as a multilayer network theory [3] called a Quantum Multiverse Network (QuMvN). The QuMvN formulation allows us to interpret the quantum wave function as a combination of ergodic Markov Chains where each Markov Chain occupies a different layer in the QuMvN structure. Layers of a QuMvN are separable components of the corresponding wave function. Single qubit measurement is defined as a state transition of the Markov Chain that emits either a $0$ or $1$ making each layer of the QuMvN a Discrete Information Source. A message is equivalent to a possible measurement outcome and the message length is the number of qubits. Therefore, the quantum wave function can be treated as a combination of multiple discrete information sources analogous to what Shannon called a "mixed" information source [18]. We show the QuMvN model has significant advantages in the classical simulation of some quantum circuits by implementing quantum gates as edge transformations on the QuMvNs. We implement a quantum virtual machine capable of simulating quantum circuits using the QuMvN model and use our implementation to classically simulate Shor's Algorithm [19]. We present results from multiple simulations of Shor's Algorithm culminating in a $70$ qubit simulation of Shor's Algorithm on a commodity cloud server with $96$ CPUS and $624$GB of RAM. Lastly, the source of quantum speedups is discussed in the context of layers in the QuMvN framework and how randomized algorithms can push the quantum supremacy boundary.
The circuit model of quantum computation is reformulated as a multilayer network theory [3] called a Quantum Multiverse Network (QuMvN). The QuMvN formulation allows us to interpret the quantum wave function as a combination of ergodic Markov Chains where each Markov Chain occupies a different layer in the QuMvN structure. Layers of a QuMvN are separable components of the corresponding wave function. Single qubit measurement is defined as a state transition of the Markov Chain that emits either a 0 or 1 making each layer of the QuMvN a Discrete Information Source. A message is equivalent to a possible measurement outcome and the message length is the number of qubits. Therefore, the quantum wave function can be treated as a combination of multiple discrete information sources analogous to what Shannon called a "mixed" information source [18]. We show the QuMvN model has significant advantages in the classical simulation of some quantum circuits by implementing quantum gates as edge transformations on the QuMvNs. We implement a quantum virtual machine capable of simulating quantum circuits using the QuMvN model and use our implementation to classically simulate Shor's Algorithm [19]. We present results from multiple simulations of Shor's Algorithm culminating in a 70 qubit simulation of Shor's Algorithm on a commodity cloud server with 96 CPUS and 624GB of RAM. Lastly, the source of quantum speedups is discussed in the context of layers in the QuMvN framework and how randomized algorithms can push the quantum supremacy boundary.
A medium-scale quantum computer with full universal quantum computing capability is necessary for various practical aims and testing applications. Here we report a 34-qubit quantum virtual machine (QtVM) based on a medium server. Our QtVM can run quantum assembly language with graphic interfaces. The QtVM is implemented with single qubit rotation gate, single to multiple controlled NOT gates to realize the universal quantum computation. Remarkably, it can realize a series of basic functions, such as, the "if" conditional programming language based on single-shot projective measurement results, "for" iteration programming language, build in arithmetic calculation. The measurement can be single-shot and arbitrary number of multi-shot types. In addition, there is in principle no limitation on number of logic gates implemented for quantum computation. By using QtVM, we demonstrate the simulation of dynamical quantum phase transition of transverse field Ising model by quantum circuits, where 34 qubits with one million gates are realized. We also show the realization of programmable Shor algorithm for factoring 15 and 35.
In the preceding chapter we established that a suitable set of quantum gates, complemented by quantum error correction, allows us to produce a desired multiqubit unitary transformation. This transformation is one of the three steps in a quantum computation; the others, of course, are the preparation of the qubits in their initial state and the measurement of them after the transformation has been implemented. A quantum computation is designed to solve a problem or class of problems. The power of quantum computers is that they can do this, at least for some problems, very much more efficiently and quickly than any conventional computer based on classical logic operations. If we can build a quantum computer then a number of important problems which are currently intractable will become solvable. The potential for greatly enhanced computational power is, in itself, reason enough to study quantum computers, but there is another. Moore’s law is the observation that the number of transistors on a chip doubles roughly every eighteen months. A simple corollary is that computer performance also doubles on the same timescale. Associated with this exponential improvement is a dramatic reduction in the size of individual components. If the pace is to be kept up then it is inevitable that quantum effects will become increasingly important and ultimately will limit the operation of the computer. In these circumstances it is sensible to consider the possibility of harnessing quantum effects to realize quantum information processors and computers. We start with a brief introduction to the theory of computer science, the principles of which underlie the operation of what we shall refer to as classical computers. These include all existing machines and any based on the manipulation of classical bits. The development of computer science owes much to Turing, who devised a simple but powerful model of a computing device: the Turing machine. It its most elementary form, this consists of four elements. (i) A tape for data storage, which acts as a memory. This tape has a sequence of spaces, each of which has on it one of a finite set of symbols. (ii) A processor, which controls the operations of the machine.
The manuscript "A Comparison of Quantum and Traditional Fourier Transform Computations" discusses a very important and often overlooked aspect of quantum computing, namely a fair and detailed comparison of a quantum algorithm, its classical simulation, and its classical counterpart taking into account the complexity of I/O. Such an article is valuable and worth publishing. The current manuscript, however, still contains some inaccuracies that should be fixed and I will make suggestion on how the presentation can be improved.Let me first summarize the main result in my own words: a quantum Fourier transform (QFT) can calculate the Fourier transform of a vector with time complexity O(log2N), compared to the complexity O(NlogN) of a classical FFT. However, if one needs to read out the full vector instead, the complexity becomes O(N polylog(N)) again, without an advantage over the classical algorithm. It is actually worse than the author discusses, if one also takes into account the complexity of loading the initial state. Loading an initial classical data vector has complexity O(N), and this has to be repeated at every repetition, giving a complexity of O(N2polylogN), worse than classical. As the author correctly mentions, the QFT is thus a useful algorithm if the input data is prepared algorithmically, and limited sampling of the result vector is sufficient, as is the case for Shor's algorithm.This is a valuable observation that deserves a paper in CiSE, since these important considerations are not all known to people outside the quantum computing community, and are sometimes ignored even by quantum computing specialists. I thus want to encourage the author to improve the presentation to make it more accessible to a broader audience and fix a couple of technical flaws.Before discussing presentation issues, I want to address one technical flaw and a few points where more clarity is needed: This statement towards the end is too simplistic and needs to be clarified: "... if we want to measure each coefficient, we must redo our operations for each coefficient (since our wave function will collapse for every measurement)." The manuscript does not explain how to read out a specific coefficient. If one samples the wave function, one measures the result and gets a certain value (s1,⋯,sN) with a probability depending on the wave function. More complex amplitude-estimation algorithms are needed to read out specific coefficients, which then takes time O(N/ϵ). This needs to be better explained. This also raises another issue of normalization and precision. The quantum wave function has to be normalized to have an L2 norm of 1. We thus need to measure to a precision of epsilon divided by the L2 norm of the classical data, and if that increases with N the scaling is even worse. For example, if all entries are of order unity, the L2 norm is N. The one technical flaw in the paper is in preparing the input state to the QFT, and the complexity of the classical simulation of the quantum algorithm. There, the numbers are wrong. The classical complexity can easily be estimated by realizing that any sparse quantum gate (such as a 1-qubit or 1-qubit gate) can be simulated in time O(N)=O(2n), where N=2n. Thus, the overhead is just O(N), not O(N2), and the simulation complexity is just O(N) times the complexity of the quantum algorithm. This will be more apparent if, as I propose below, the author shows the quantum algorithm also through a sequence of quantum gates. However, note that in the simulation we then have the full vector, and thus do not incur the overhead of quantum state tomography. We need to simulate the algorithm only once and not O(N/ϵ) times. This means the simulation remains at O(Nlog2N) even if we read out all entries, which is not bad compared to the classical O(NlogN) of the FFT. The reason why the author seems to end with a different complexity is that his Matlab simulation does not simulate the quantum algorithm but the computation of the effect of the QFT applied to just one basis state. That is a suboptimal implementation. I thus propose to replace the Matlab code by a discussion of how a quantum gate (Hadamard or controlled phase rotation) can be implemented, and that will then nicely give the scaling discussed above.As mentioned in my summary at the beginning, the value of the paper can be increased if the author could also discuss the complexity of quantum state preparation from classical input data, e.g., following Shende-Bullock-Markov \citep{markov2006}, which has a complexity of O(Nlogϵ1). That means, that if the data is read from a classical vector (and not computed as, e.g., in Shor's algorithm), then the complexity of state preparation of O(Nlogϵ1) completely dominates the QFT itself, and if one furthermore wants to read out the full vector instead of sampling it, the complexity becomes O(N2log2(ϵ1)).In the conclusion the author writes that "QEC research is still in very early development and it is currently difficult to determine how the required resources for these corrections could scale with qubit usage." That is incorrect, as the overhead is pretty well known by now for certain QEC codes, such as the surface code. The asymptotic scaling of the overhead has long been known, and also detailed resource costs have been worked out for various algorithms. I suggest to focus the QEC section on the need for fault tolerance, and the large overhead associated with it. This is definitely not something that can be done on NISQ devices at an interesting scale. I would also use another reference for QEC than the Gil Kalai paper.Now, to suggestions for improved presentation:In the abstract, I suggest to present fewer technical details. "radix-2 DIT case of the Cooley-Tukey Algorithm" can just be called Fast Fourier transform, the QUBIT4MATLAB package does not need to be mentioned in the abstract, and neither does the "Master Theorem" have to be mentioned.In the abstract and in the rest of the paper, it is also better to talk about quantum speedup and not quantum supremacy. The paper is about asymptotic scaling (the author uses the big-O notation throughout), and not about supremacy, which is a specific size problem that is solved better on quantum hardware rather than classical hardware. A supremacy claim needs all constants to be worked out, and assumptions for the specific classical and quantum hardware. Replacing quantum supremacy by quantum speedup can fix this. The observations are still valuable and correct.The first section is called "The shortcomings of classical computing and the early developments of quantum computing". That title sounds strange to me. What are the shortcomings? The author may rather want to stress the additional capabilities of quantum computers. Given that most readers will not be physicists and have no experience with quantum mechanics, it would be valuable to expand this first section. Discuss equation (3) before equation (1), and then introduce equation (1), to show that this means that the state of a qubit is actually a two-dimensional complex vector, After that only go to the many-quit state. After equation 4 it may be good to talk about amplitudes first, and then probabilities. Saying that the state is determined by "the qubit simply has a probability...", ignores the all important phases that are the crucial difference between quantum computing and probabilistic classical computing. "Quantum gates, unlike classical gates, do not delete information and are fully reversible." Needs further explanation. This comes from the reversibility of the microscopic laws of physics. Here it may be worthwhile to mention that, as quantum gates are time evolution of a quantum system, they are unitary operators on the Hilbert space that was introduced above. The discussion in the next sentence about them not using energy is misleading as well. In fact, the control and operation of the quantum gate always needs energy. It is only the free evolution of a quantum system that conserves energy. The part on " subatomic systems such as a superposition of quantum states. " would also need more explanation. Does the author here want to describe specific implementations of qubits? If so, more detail is needed. If not, I propose to drop this part."The definition and use of the classical discrete Fourier transform": here is an abrupt jump from Shor's algorithm to the DFT. Since Shor's algorithm again gets mentioned later on as a case where the QFT is better than a classical DFT, it make sense to discuss more details of Shor's algorithm, and that in essence it solvers the factor problem by using a QFT to find the period of a function. In light of the above complexity discussion this is important: we don't deal with classical data that one has to load but with a state that is computed (the function f(x) = a^x mod N ), and one is not interested in the full vector but just in finding the period. This can be done just by measuring the result of the QFT, which in this particular case will return a random multiple of the base frequency, and with a few repeated measurements one can then extract the period).The Fourier transform should be well known to the reader, and it is thus not obvious to me that equation 6 is needed. I would instead introduce \omega in equation 5. For the discussion of the implementation I suggest to mention that the rest of the paper limits itself to the case of powers of 2, i.e. N=2^n, for which the radix-2 version applies. Since the implementation is well known for most computational scientists, it could be moved from to supplementary material, as can be the derivation of the O(N log N) complexity, which is also well known.In the discussion of the QFT, unfortunately the quantum algorithm is not presented. What is presented is the mathematical unitary operation. It would be very valuable for the reader to see an actual implementation of the quantum algorithm, i.e. the sequence of O(n^2) Hadamard gates and controlled rotations – either as a circuit drawing, or more useful as quantum code, either using a quantum programming language that allows loops (such as Q#), or as some quantum pseudo code with loops. Then the reader will see the sequence of O(n^2) operations and how it creates the unitary operation of the QFT."The implementation of the QFT in MATLAB...". This section can be improved as well., As discussed above, the Matlab code does not implement the quantum algorithm but rather implements the application of the unitary operation to one of the basis states. It would be more useful for the reader to instead get implementations of the Hadamard and controlled phase gates, which could then be combined with the above quantum algorithm (maybe all in Matlab even?) for a full simulation of the algorithm – and in time O(N n^2), not O(N^2 n^2)."Evaluating the complexity of the QFT Implementation" – I discussed the issues with the complexity estimates already above. If one replaces it by an estimate of the complexity of simulating the H and controlled phase gate each in O(N) operations then it both becomes simpler and the complexity becomes just O(N) times that of the quantum version"Evaluating the complexity of the theoretical form of the QFT Implementation”. I assume that by "theoretical" the author means the actual quantum operation? The comparison section needs to be fixed, since that's where there is the mentioned flaw based on the suboptimal Matlab code, and that will also change table 1. I suggest that table 1 could have three cases: A) ignoring state preparation and one only wants to sample the output a constant number of times; B) ignoring state preparation but one wants to read the full vector; C) including state preparation from classical data and one only wants to sample the output a constant number of times; D) including state preparation from classical data and one wants to read the full vectorThe reader will then see that only case A has a speedup, and that in the other cases even the simulation of the quantum algorithm is faster than the quantum algorithm on a quantum computer.The conclusions should then be updated, taking these slightly modified comparisons into account. The case of Shor's algorithm, which falls into category A) above, is indeed interesting but deserves a deeper explanation so that the reader understands that Shor's algorithm can compute the input with complexity O(N3) (up to log factors), and why only a few samples of the output are needed. That way, the exponential speedup over the FFT remains, and the super polynomial speedup over the name sieve. However, if classical data has to be loaded or should be returned then there is no speedup. I call this the I/O problem of quantum algorithms, which indeed—as the author writes—means that in these cases quantum computing is no better than classical computing.This is an important observation that the paper beautifully works out. Fixing the flaw in the simulation section and improving the presentation will make this a very nice paper.
Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by simulating a Markov chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.
A quantum network is believed to be the next generation of quantum technology [1]. In the past decades, individual quantum systems—for example, quantum dot (QD) [2–4], etc.—have been studied in depth and the technologies are mature; therefore, the consideration of combining different systems to construct a quantum network (especially a hybrid one) is timely. Moreover, a quantum network is absolutely necessary in the fulfilment of a general quantum task, which needs the cooperation of many different kinds of quantum units. On a larger scale, the local quantum networks can be further linked to construct a global quantum network, namely the quantum Internet [1]. With this technology at hand, distributed quantum computation can be realized, making scalable quantum information processing possible in multiple sites over long distances. The primary challenge of the construction of a quantum network is the state distribution among different nodes. An elementary quantum network based on two identical nodes each constituted by a single atom in the optical cavity has been realized in an experiment [5]. However, here we focus on the quantum network comprising heterogeneous nodes, which is more general and can combine advantages of different quantum systems to complete more complicated quantum tasks. The construction of a hybrid quantum network is more difficult, since heterogeneous quantum systems have different properties that are not naturally matched, such as the different emission (or absorption) wavelengths and different bandwidths [8], etc. To establish the hybrid interface, QD is a good candidate. QD can act as a deterministic single [2] or entangled [3] photon source and is also a promising physical carrier for solid-state spin qubit [4]. QD has been interfaced with hot atoms [6] and single ions [7] in recent years. Almost at the same time, Li's group experimentally demonstrated the first optical connection between QD and a solid-state quantum memory [8]. Distinguishing from the former works, the all-solid-state character of this work makes the whole architecture more stable and easier to be manipulated and integrated. During this work, the sample was grown by Niu's group [8]. A special sample design moves the emission band of QDs to approximately 879.7 nm—the memory band of the solid-state memory [9]. Since the fine-tuning range is only several 0.1 nm, hundreds of QDs on the sample were detected by Li et al. and finally one of them was selected, whose emission line is located at 879.5 nm. Using a local-heating technique, the researchers precisely tuned the emission wavelength of this QD to the solid-state memory's memory band, whose bandwidth is as narrow as hundreds of MHz [9]. The quantum memory in this experiment was based on the atomic frequency comb (AFC) protocol [10]. The memory efficiency is as high as 20% when the storage time is 40 ns, and the non-collinear configuration for the pump light and the signal photons can substantially reduce the noise from the pump light. To further reduce the detection noise, a superconducting single-photon detector (SSPD), whose dark count rate can be as low as 1.5 per second, is used instead of the silicon single-photon avalanche diode. With these conditions, Li's experiment clearly shows the stored and retrieved single photons that are originally generated from the QD. The signal-to-noise ratio (SNR) is 9:1. The second-order retrieved single photons are even seen in the data, which further validates the experimental result. Another advantage of Li's work is the demonstration of multi-temporal-mode quantum memory with up to 100 narrow deterministic-single-photon pulses [8]. This result is directly associated with the construction of a quantum repeater [11]—one of the essential components for a long-distance quantum network. The primary characteristics of this experiment, namely the deterministic single-photon memory (differing from the previous works) and the multimode memory, are both critically important in the improvement of a quantum repeater's efficiency [12]. Also, Li's further work finished the quantum memory of 51 spatial modes using the orbital angular momentum (OAM) modes of herald single photons [9]. By combining both the temporal and spatial multiplexing, and the deterministic single-photon source, more efficient quantum repeaters can be constructed. We hope that the recent studies [8,9] will pave the way for the construction of quantum repeaters, and furthermore quantum networks—both in the short term and the long term—based on all-solid-state devices. As a special application of a quantum network, quantum key distribution (QKD) can also benefit from Li's work both in security and transmission distance (key rate). QKD utilizes the principles of quantum mechanics to guarantee secure communication between two authorized parties (or quantum nodes, for instance) and the famous protocols including BB84 (proposed by Bennett and Brassard in 1984) [13]), etc. However, the commonly used weak-coherent-pulse photon source (typically attenuated laser) will decrease the security of QKD because of its multiphoton probability, which means that QKD suffers from several certain attacks, such as the photon number splitting (PNS) attack. Although a decoy state has been introduced to achieve potential solutions to this problem, a substantial shrinking of the sifted key will be required and the complexity of the protocol may contain loopholes [14,15]. Therefore, the unconditional security guaranteed by quantum mechanics still requires a single-photon source, such as QD (experimental work regarding QKD on the basis of a QD single-photon source can be referred to in [14,15]), etc. The deterministic-single-photon pulse train generated by QD in Li's experiment [8] can provide a single-photon-source node (in the network) and keep the security of QKD. Moreover, because of both the elimination of multiphoton probability and the multi-temporal-mode single-photon generation, the key rate of QKD will be improved, which is associated with a longer transmission distance. The quantum repeater that benefited from Li's work will also further improve the transmission distance of QKD.
Quantum computing is a promising approach of computation that is based on equations from Quantum Mechanics and nanotechnology. Understanding and simulating quantum operations on a classical computer has different approaches and is modeled in different ways. However, the most repute ways are Quantum Turing Machine, Network Model or circuit model of connected gates and Quantum Programming Language. Many simulators do exist that varies in many features such as implementation languages, target platforms, paradigms, visuality, and applied quantum algorithms. There was a developmental trade-off between the simplicity and the functionality of the simulator. The goals and research activities are outlined as follows: First, surveying the quantum computing world, its characteristics, issues, problems, and challenges. Second, surveying the existing quantum simulators, illustrating representative simulators of major approaches, their features, and functionalities. Third, introducing a framework to provide the power of quantum computing , while insisting the simplicity and high usability. Finally, providing a case study for a new quantum algorithm based on the introduced framework.