According to
https://www.quora.com/Are-there-any-working-quantum-computers-yet
They are only experimentally
Apparently: https://www.research.ibm.com/ibm-q/ and https://ai.google/research/teams/applied-science/quantum-ai/ at least.
D-Wave statistical quantum computer is a working quantum computer.
Dear Najla Matti:
Congratulations and thank you so much for asking this most important question! In this way, scientists must determine still many relative computational complexities so that they will get to work a quantum computer. However, a lot of research is currently being carried out. For instance, Farhi et al. (2001) point out that continuous time evolution may offer an alternative model for the design of a quantum computer and that a large quantum computer has yet to be built, but the rules for programming such a device, which are derived from the laws of quantum mechanics, are well established. These authors state that it is already known that quantum computers could solve problems believed to be intractable on classical computers. In doing so, they highlight that quantum computation by adiabatic evolution applied to a Satisfiability problem will succeed if the running time is long enough. Farhi et al. (2001) reveal, then, that this follows from the quantum adiabatic theorem, which is in a form that allows it to be applied to a wide variety of combinatorial search problems. As a result, they observe evidence that for their randomly generated small instances of Exact Cover the required running time grows slowly as a function of the number of bits. Likewise, Farhi et al. (2001) explain that it is possible that the slow growth they spot indicates the true asymptotic behavior of the algorithm when applied to randomly generated hard instances of Exact Cover. As an example, Farhi et al. (2001: 6) undertake highly focused research on Simulating a quatum computer. They highlight that the ingredients of the quantum adiabatic evolution algorithm are (i) an instance-dependent, time-dependent Hamiltonian H(t) given by (8) (ii) an initial state ψ(0) =ψg(0) given by (4) (iii) evolution from 0 to T according to the Schr¨odinger equation (1) (iv) a measurement of ψ(T) . In order to simulate this quantum computer they numerically integrate the Schr¨odinger equation in (iii). For an n-qubit quantum system the state vector ψ(t) has 2n complex components. For n = 20 this means numerically integrating a differential equation with 2,097,152 real variables. This is as large a system as they could handle with our computer resources in a few months of running. Because the number of bits in our instances of Exact Cover is never more than 20, as stated by these authors, we can always determine if the instance has satisfying assignments and what they are. They do this by exhaustively checking, at 20 bits, all 220-bit assignments, which takes virtually no time on a classical computer. Admittedly, they are only able to study the performance of the quantum computer on instances that are easy for a classical computer. The classical simulation of a quantum computer is itself a classical algorithm but not a good one. Ingredient (iv) of the quantum algorithm is the measurement. However, in their numerical simulation they do not simulate the measurement. Rather, since they compute the 2n coefficients of ψ(T), they simply read off the coefficients corresponding to satisfying assignments, if there are any. The sum of the squared magnitudes of these coefficients gives the probability that the actual measurement would produce a satisfying assignment.
Therefore, Farhi et al. (2001) emphasize that if this quantum adiabatic algorithm does actually outperform known classical algorithms, we would have reason to eagerly await the construction of a quantum computer capable of running it.
Progressing in the exposed sense, Montanaro (2016) brings out to the open that quantum computers are designed to outperform standard computers by running quantum algorithms. Like this manner, as stated by this author, in the early days of classical computing, one of the main applications of computer technology was the simulation of physical systems (such applications arguably go back at least as far as the Antikythera mechanism from the 2nd century BC.). Similarly, the most important early application of quantum computers is likely to be the simulation of quantum systems. Applications of quantum simulation include quantum chemistry, superconductivity, metamaterials and high-energy physics. Indeed, one might expect that quantum simulation would help us understand any system where quantum mechanics has a role. The word ‘simulation’ can be used to describe a number of problems, but in quantum, computation is often used to mean the problem of calculating the dynamical properties of a system. This can be stated more specifically as: given a Hamiltonian H describing a physical system, and a description of an initial state j i ψ of that system, output some property of the state ψt j i ¼ e - iHtj i ψ corresponding to evolving the system according to that Hamiltonian for time t. As all quantum systems obey the Schrödinger equation, this is a fundamentally important task; however, the exponential complexity of completely describing general quantum states suggests that it should be impossible to achieve efficiently classically, and indeed no efficient general classical algorithm for quantum simulation is known. This problem originally motivated Feynman to ask whether a quantum computer could efficiently simulate quantum mechanics. A general-purpose quantum computer can indeed efficiently simulate quantum mechanics in this sense for many physically realistic cases, such as systems with locality restrictions on their interactions. Given a description of a quantum state j i ψ , a description of H, and a time t, the quantum simulation algorithm produces an approximation to the state ψt j i. Measurements can then be performed on this state to determine quantities of interest about it. The algorithm runs in time polynomial in the size of the system being simulated (the number of qubits) and the desired evolution time, giving an exponential speedup over the best general classical algorithms known. However, there is still room for improvement and quantum simulation remains a topic of active research. Examples include work on increasing the accuracy of quantum simulation while retaining a fast runtime; optimizing the algorithm for particular applications such as quantum chemistry; and exploring applications to new areas such as quantum field theory. The above, very general, approach is sometimes termed digital quantum simulation: we assume we have a large-scale, general purpose quantum computer and run the quantum simulation algorithm on it. By contrast, in analogue quantum simulation we mimic one physical system directly using another. That is, if we would like to simulate a system with some Hamiltonian H, then we build another system that can be described by a Hamiltonian approximating H. We have gained something by doing this if the second system is easier to build, to run or to extract information from than the first. For certain systems analogue quantum simulation may be significantly easier to implement than digital quantum simulation, at the expense of being less flexible. It is therefore expected that analogue simulators outperforming their classical counterparts will be implemented first.
Bibliographical references
- Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001). A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science, 292(5516), 472-475. Retrieved from: (https://arxiv.org/pdf/quant-ph/0104129.pdf). [Accessed July 23, 2019].
- Montanaro, A. (2016). Quantum algorithms: an overview. npj Quantum Information, 2, 15023. Retrieved from: (https://www.nature.com/articles/npjqi201523.pdf?origin=ppub). [Accessed July 16, 2019].
Warm regards,
Javier.
QUANTUM COMPUTING: ARTIFICIAL INTELLIGENCE AND THE POSSIBLE IMPACT OF THEIR LARGE-SCALE THEORETICAL AND PRACTICAL FRAMEWORK ON FUTURE DEVELOPMENTS IN THE FIELD OF SCIENTIFIC COMPUTING
Scientists must determine still many relative computational complexities so that they will get to work a quantum computer. However, a lot of research is currently being carried out. For instance, Farhi et al. (2001) point out that continuous time evolution may offer an alternative model for the design of a quantum computer and that a large quantum computer has yet to be built, but the rules for programming such a device, which are derived from the laws of quantum mechanics, are well established. These authors state that it is already known that quantum computers could solve problems believed to be intractable on classical computers. In doing so, they highlight that quantum computation by adiabatic evolution applied to a Satisfiability problem will succeed if the running time is long enough. Farhi et al. (2001) reveal, then, that this follows from the quantum adiabatic theorem, which is in a form that allows it to be applied to a wide variety of combinatorial search problems. As a result, they observe evidence that for their randomly generated small instances of Exact Cover the required running time grows slowly as a function of the number of bits. Likewise, Farhi et al. (2001) explain that it is possible that the slow growth they spot indicates the true asymptotic behavior of the algorithm when applied to randomly generated hard instances of Exact Cover. As an example, Farhi et al. (2001: 6) undertake highly focused research on Simulating a quatum computer. They highlight that the ingredients of the quantum adiabatic evolution algorithm are (i) an instance-dependent, time-dependent Hamiltonian H(t) given by (8) (ii) an initial state ψ(0) =ψg(0) given by (4) (iii) evolution from 0 to T according to the Schr¨odinger equation (1) (iv) a measurement of ψ(T) . In order to simulate this quantum computer they numerically integrate the Schr¨odinger equation in (iii). For an n-qubit quantum system the state vector ψ(t) has 2n complex components. For n = 20 this means numerically integrating a differential equation with 2,097,152 real variables. This is as large a system as they could handle with our computer resources in a few months of running. Because the number of bits in our instances of Exact Cover is never more than 20, as stated by these authors, we can always determine if the instance has satisfying assignments and what they are. They do this by exhaustively checking, at 20 bits, all 220-bit assignments, which takes virtually no time on a classical computer. Admittedly, they are only able to study the performance of the quantum computer on instances that are easy for a classical computer. The classical simulation of a quantum computer is itself a classical algorithm but not a good one. Ingredient (iv) of the quantum algorithm is the measurement. However, in their numerical simulation they do not simulate the measurement. Rather, since they compute the 2n coefficients of ψ(T), they simply read off the coefficients corresponding to satisfying assignments, if there are any. The sum of the squared magnitudes of these coefficients gives the probability that the actual measurement would produce a satisfying assignment.
Therefore, Farhi et al. (2001) emphasize that if this quantum adiabatic algorithm does actually outperform known classical algorithms, we would have reason to eagerly await the construction of a quantum computer capable of running it.
Progressing in the exposed sense, Montanaro (2016) brings out to the open that quantum computers are designed to outperform standard computers by running quantum algorithms. Like this manner, as stated by this author, in the early days of classical computing, one of the main applications of computer technology was the simulation of physical systems (such applications arguably go back at least as far as the Antikythera mechanism from the 2nd century BC.). Similarly, the most important early application of quantum computers is likely to be the simulation of quantum systems. Applications of quantum simulation include quantum chemistry, superconductivity, metamaterials and high-energy physics. Indeed, one might expect that quantum simulation would help us understand any system where quantum mechanics has a role. The word ‘simulation’ can be used to describe a number of problems, but in quantum, computation is often used to mean the problem of calculating the dynamical properties of a system. This can be stated more specifically as: given a Hamiltonian H describing a physical system, and a description of an initial state j i ψ of that system, output some property of the state ψt j i ¼ e - iHtj i ψ corresponding to evolving the system according to that Hamiltonian for time t. As all quantum systems obey the Schrödinger equation, this is a fundamentally important task; however, the exponential complexity of completely describing general quantum states suggests that it should be impossible to achieve efficiently classically, and indeed no efficient general classical algorithm for quantum simulation is known. This problem originally motivated Feynman to ask whether a quantum computer could efficiently simulate quantum mechanics. A general-purpose quantum computer can indeed efficiently simulate quantum mechanics in this sense for many physically realistic cases, such as systems with locality restrictions on their interactions. Given a description of a quantum state j i ψ , a description of H, and a time t, the quantum simulation algorithm produces an approximation to the state ψt j i. Measurements can then be performed on this state to determine quantities of interest about it. The algorithm runs in time polynomial in the size of the system being simulated (the number of qubits) and the desired evolution time, giving an exponential speedup over the best general classical algorithms known. However, there is still room for improvement and quantum simulation remains a topic of active research. Examples include work on increasing the accuracy of quantum simulation while retaining a fast runtime; optimizing the algorithm for particular applications such as quantum chemistry; and exploring applications to new areas such as quantum field theory. The above, very general, approach is sometimes termed digital quantum simulation: we assume we have a large-scale, general purpose quantum computer and run the quantum simulation algorithm on it. By contrast, in analogue quantum simulation we mimic one physical system directly using another. That is, if we would like to simulate a system with some Hamiltonian H, then we build another system that can be described by a Hamiltonian approximating H. We have gained something by doing this if the second system is easier to build, to run or to extract information from than the first. For certain systems analogue quantum simulation may be significantly easier to implement than digital quantum simulation, at the expense of being less flexible. It is therefore expected that analogue simulators outperforming their classical counterparts will be implemented first.
Likewise, Singh (2019) presents an overview of the issues surrounding what Quantum Computing is and how it is useful for Artificial Intelligence (AI). Like this, this author considers the question of why quantum computers remain largely theoretical, as she indicates that still many obstacles must be overcome so that, for example, quantum mechanics and quantum computing will help solve problems on a huge scale, or so that scientists will be able to make important advances in Medical Research. However, Singh (2019) highlights that quantum technology will eventually deliver a computing revolution.
In the same way, Möller and Vuik (2017) address the potential of quantum algorithms to bring major breakthroughs in applied mathematics and its applications, and subsequently, they give several examples that demonstrate the possible impact of quantum-accelerated scientific computing on society. Like this manner, for instance, they draw attention to one of the most basic problems in scientific computing:
One of the most basic problems in scientific computing is the solution of systems of linear equations Ax=bAx=b where A is an invertible N×NN×N matrix and b a vector of size N. The most naive solution of this problem is Gaussian elimination without exploiting the system’s sparsity pattern and it runs in time O(N3)O(N3). If A is d-sparse, that is, each row contains at most d≪Nd≪Nentries, then the runtime of classical algorithms still scales at least linearly in N. This also applies to any quantum algorithm if the desired output is the solution vector x which requires time O(N)O(N) just for being written out.
We can notice, then, as stated by Möller and Vuik (2017), that quantum-enhanced scientific computing is an exciting new field that has the highest chances to become a game-changing technology if quantum hardware gets integrated into conventional HPC systems and used as special-purpose accelerators for those tasks for which efficient quantum algorithms exist. First and foremost, Möller and Vuik (2017) bring out to the open that quantum computers, quantum algorithms, and quantum principles are very different from all what we are used to know from classical computing based on digital circuits. However, these authors underscore that classical computing also needs drastic changes to overcome its omnipresent limitations, namely, the memory wall, the energy wall, and the instruction-level parallelism wall.
Bibliographical references
- Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001). A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science, 292(5516), 472-475. Retrieved from: (https://arxiv.org/pdf/quant-ph/0104129.pdf). [Accessed July 23, 2019].
- Montanaro, A. (2016). Quantum algorithms: an overview. npj Quantum Information, 2, 15023. Retrieved from: (https://www.nature.com/articles/npjqi201523.pdf?origin=ppub). [Accessed July 16, 2019].
- Möller, M., & Vuik, C. (2017). On the impact of quantum computing technology on future developments in high-performance scientific computing. Ethics and Information Technology, 19(4), 253-269. https://doi.org/10.1007/s10676-017-9438-0. Retrieved from. (https://link.springer.com/article/10.1007/s10676-017-9438-0#copyrightInformation). [Accessed August 03, 2019]. .
- Singh. D. (2019). What is Quantum Computing and How is it Useful for Artificial Intelligence? Data Science Central. Retrieved from: (https://www.datasciencecentral.com/profiles/blogs/what-is-quantum-computing-and-how-is-it-useful-for-artificial). [Accessed August 03, 2019].
- Badges
- Science topic
- Similar topics
- Computer Communications (Networks)
- Simulators