What is Quantum computation: Definition and 77 Discussions

Quantum computing is the exploitation of collective properties of quantum states, such as superposition and entanglement, to perform computation. The devices that perform quantum computations are known as quantum computers. They are believed to be able to solve certain computational problems, such as integer factorization (which underlies RSA encryption), substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science. Expansion is expected in the next few years as the field shifts toward real-world use in pharmaceutical, data security and other applications.Quantum computing began in 1980 when physicist Paul Benioff proposed a quantum mechanical model of the Turing machine. Richard Feynman and Yuri Manin later suggested that a quantum computer had the potential to simulate things a classical computer could not feasibly do. In 1994, Peter Shor developed a quantum algorithm for factoring integers with the potential to decrypt RSA-encrypted communications. Despite ongoing experimental progress since the late 1990s, most researchers believe that "fault-tolerant quantum computing [is] still a rather distant dream." In recent years, investment in quantum computing research has increased in the public and private sectors. On 23 October 2019, Google AI, in partnership with the U.S. National Aeronautics and Space Administration (NASA), claimed to have performed a quantum computation that was infeasible on any classical computer.There are several types of quantum computers (also known as quantum computing systems), including the quantum circuit model, quantum Turing machine, adiabatic quantum computer, one-way quantum computer, and various quantum cellular automata. The most widely used model is the quantum circuit, based on the quantum bit, or "qubit", which is somewhat analogous to the bit in classical computation. A qubit can be in a 1 or 0 quantum state, or in a superposition of the 1 and 0 states. When it is measured, however, it is always 0 or 1; the probability of either outcome depends on the qubit's quantum state immediately prior to measurement.
Efforts towards building a physical quantum computer focus on technologies such as transmons, ion traps and topological quantum computers, which aim to create high-quality qubits. These qubits may be designed differently, depending on the full quantum computer's computing model, whether quantum logic gates, quantum annealing, or adiabatic quantum computation. There are currently a number of significant obstacles to constructing useful quantum computers. It is particularly difficult to maintain qubits' quantum states, as they suffer from quantum decoherence and state fidelity. Quantum computers therefore require error correction.Any computational problem that can be solved by a classical computer can also be solved by a quantum computer. Conversely, any problem that can be solved by a quantum computer can also be solved by a classical computer, at least in principle given enough time. In other words, quantum computers obey the Church–Turing thesis. This means that while quantum computers provide no additional advantages over classical computers in terms of computability, quantum algorithms for certain problems have significantly lower time complexities than corresponding known classical algorithms. Notably, quantum computers are believed to be able to quickly solve certain problems that no classical computer could solve in any feasible amount of time—a feat known as "quantum supremacy." The study of the computational complexity of problems with respect to quantum computers is known as quantum complexity theory.

View More On Wikipedia.org
  1. benagastov

    Error while Executing "Make all" code for Quantum Espresso in Colab

    Good evening, Now I start learning Quantum Espresso and I tried to install it on Google Colab, since I already get convenient and its my habit to do all computation in Physics using google Colab. Sometimes I rent cloud gpu if I need bigger RAM and GPU when I have heavy load. You can see the...
  2. cwill53

    Basic Quantum Circuit: States of Individual Qubits

    I have done part A so far below, but I'm a bit behind on my reading, so I don't quite understand the action of the controlled-NOT gate on a single qubit. What I have so written so far for part B is: Let ##\mathcal{H}=(\mathbb{C}^2)^{\otimes 3}##. Let ##|\psi _{q_i}\rangle_k## , ##(i\in\left...
  3. Llukis

    I Discover Beginner-Friendly Books on Quantum Information and Computation | Q&A

    Hello to everyone, I would like to ask you to brief questions. The first one is whether you could recommend any pedagogical books on Quantum Information and Computation. I tried Nielsen and Chuang but I found it too dense for a beginner in the field. The second question is the following: to...
  4. A

    I Counterfactual quantum computation on interferometer

    I watched a video on the topic by Sabine Hossenfelder. Now it is said by many that this proves the photon "knows" something in advance because a certain state of a certain beam splitter can be probed in theory without the photon ever encountering that beam splitter because it took another path...
  5. A

    I Quantum computation and entropy

    Quantum gates must be reversible. The usual justification for this is that in QM the time evolution of a system is a unitary operator which, by linear algebra, is reversible (invertible). But I am trying to get a better intuition of this, so I came up with the following explanation: In order to...
  6. J

    Preparing for a Quantum Computation Course: Superconducting Qubits

    Summary:: Looking for articles/books to prepare myself for the course: Quantum computation with superconducting qubits Hello everyone. I am about to take a course in Quantum computation with superconducting qubits and I am searching for material to prepare it. I took a first course on that...
  7. llha

    I [Quantum Computing] Quantum Parallelism State Calculation

    Hi, I'm going through Nielsen and Chuang's Quantum Computation and Quantum Information textbook and I don't really understand this part about quantum parallelism: Shouldn't the resulting state be (1/sqrt(2^4)) * (|0, f(0)> + |0, f(1)> + |1, f(1)> + |1, f(0)>), since the resulting state would...
  8. porton

    I Are electrons universal problem solvers?

    Existence of an universal problem solver, a polynomial-time NP-complete algorithm is a $1000000 prize question. But suppose that we were able to know something "simple", e.g. an electron state or electron wave function exactly. Would we be able to solve complex mathematical problems (like...
  9. A

    A Are all quantum computers feedforward networks?

    Hi! I am trying to understand how advanced quantum computers have in fact become as well as how advanced they can in principle become. To probe these issues, I am asking the group whether or not quantum computers are restricted to feedforward processing, both currently and in principle? Here is...
  10. ubergewehr273

    I Extraction of a particular quantum state from a quantum circuit

    Hello everyone! I'm trying to implement a quantum circuit that yields a superposition state $$\frac{1}{\sqrt{2}} (|01 \rangle + |10 \rangle)$$ I'm using parameterized gates to achieve this. I have been able to create the state $$\frac{1}{\sqrt{2}}(|01\rangle + e^{i\phi} |10 \rangle)$$ Is there...
  11. B

    A Quantum Period is Compression Robust

    https://arxiv.org/abs/1905.10074 The paper finds that one can reduce the number of qubits to a constant (just one works) used in the last, modular exponential register of the variants of Shor's algorithm, used to factor integers and find discrete logarithms, by applying a universal hash...
  12. tomdodd4598

    I Number of qubits required for Shor's algorithm to factor a number < 2^n

    Hey there, There are plenty of proposed implementations of Shor's algorithm which require different numbers of qubits, ##q##, to be able to factor a number ##N## of size ##<2^n##, i.e. a number of length at most ##n## bits. Most of these require ##q## linear in ##n##; for example, this...
  13. Quark Effect

    B What is the significance of 'i' in quantum computation notation?

    Hi guys, I am currently having some difficulties with this quantum state. I don't entirely understand what that letter 'i' means, where it comes from and why it appears in brackets [1, i]. Shouldn't there be a '0' instead? I am an absolute beginner in quantum computation. I've been following a...
  14. G

    Programs Quantum Computation and Information Master's Degree

    I'm in a Physics BSc programme and I would like to delve into quantum computation and quantum information. There are two master's degree in Europe that I find interesting in particular: Quantum Engineering MSc at ETH Zurich and Applied Physics MSc at TU Delft (track in Quantum Devices and...
  15. ngrunenberg

    B How do quantum computers find a solution?

    Apologies in advance if this is a stupid question, I'm not the brightest. I recently listened to Scott Aaronson's conversation with Lex Fridman, and an interview he did for Scientific American, regarding quantum computing (QC from now on) and have a question regarding how a QC finds a solution...
  16. Quantum Alchemy

    I How does Classical Physics explain Quantum Entanglement?

    As a Computer Programmer, it's hard to wrap my head around Quantum Entanglement and non locality being explained in the context of Classical Physics. In other words, if the universe at it's core is physical where does Quantum Entanglement fit within a physical picture of reality? There's been...
  17. Auto-Didact

    Google: Demonstrating Quantum Supremacy

    Here is the paper, published today in Nature: Arute et al. 2019, Quantum supremacy using a programmable superconducting processor
  18. E

    Quantum gravity and quantum cosmology books

    At the risk of annoying some people but hopefully also interesting others I would like to mention my new book on the periodic table, which has just been named as one of 7 "outstdanding academic books of the year 2007" in the category for chemistry But the book is as much about physics as it...
  19. P

    I Quantum Computing - projection operators

    Assume ##P_1## and ##P_2## are two projection operators. I want to show that if their commutator ##[P_1,P_2]=0##, then their product ##P_1P_2## is also a projection operator. My first idea was: $$P_1=|u_1\rangle\langle u_1|, P_2=|u_2\rangle\langle u_2|$$ $$P_1P_2= |u_1\rangle\langle...
  20. Haorong Wu

    [Quantum Computing] Verify a circuit implementing and operation

    This is an exercise from "Quantum search as a quantum simulation " in Chapter "Quantum search algorithms". The circuit is shown as the following picture. For small time interval, the effect of the operation in the problem statement could be written as ## exp \left ( -i \left | \psi \right >...
  21. Haorong Wu

    I Confusion about factoring in quantum computation

    Hi, I'm currently learning QC with Nielsen's QCQI. I've written a program in Matlab following the factoring algorithm in page 233 and 235. I run the program for factoring 15, 18, and 25. I got the proper results several times, but I also got error reports sometime, especially when factoring 18...
  22. Haorong Wu

    Quantum A book about problems of quantum computation?

    Summary: A book about problems of quantum computation? I remember that there is a book containing many problems of quantum computation, but I can't find the page or post now. I have hard time learning quantum computation. Thus, I want to try to solve problems in order to get a solid...
  23. Haorong Wu

    Schools Are there any good groups about quantum computation?

    Hi. After learning quantum computation for months, it fascinates me. Quantum computation expands my view about computational methods. I believe that many future achievements can be obtained from quantum computing, especially the combination of AI and quantum computation. Meanwhile, I think...
  24. I

    Programs Topics at the junction of AdS/CFT and quantum information

    I have been asked to draft a (informal) research proposal for a PhD thesis. I have some background in quantum information and my interests are leaning towards the AdS/CFT correspondence. I was wondering if you could suggest a few (preferably recent) theory papers at the junction of quantum...
  25. Haorong Wu

    I Is there a procedure for designing some quantum circuits?

    In Nielsen's book, the chapter of quantum circuits does not describe explicitly any procedures to design a circuit. For example, given the matrix of Fredkin gate, ##\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1...
  26. Haorong Wu

    I The Schmidt decomposition in QC

    Hi, there. I have some problems when learning Schmidt decomposition in Nielsen's QC. The statement of Schmidt decomposition is simple and clear, however, the book doesn't give a clear procedure to do the Schmidt decomposition. I don't know whether the proof under the theorem is the the one I...
  27. Haorong Wu

    I How to understand the Bloch sphere in the quantum computation?

    I've read that ##\left | \psi \right > =cos \frac \theta 2 \left | 0 \right > + e^{i \phi} sin \frac \theta 2 \left | 1 \right >##, and the corresponding point in the Bloch sphere is as the fig below shows. I think ##\left | 0 \right >## and ##\left | 1 \right >## are orthonormal vectors...
  28. Haorong Wu

    Courses Is Griffiths' QM sufficient before studying quantum computation?

    Hello, again. My current interest is quantum computation. I've finished Griffiths' QM for the first time. Because it only takes me a month studying the book, I may have study it superficial, so I plan to study it again and complete all the problems after each chapter. Then is this book...
  29. Q

    I Will quantum computation lower energy requirements?

    According to this article, written by D-Wave's CEO, the advent of quantum computers will "change the way the world uses energy". However, on a first reading, it sounds like an advertorial that pushes nonsense. I'm no energy scientist (unless you put high energy physics in that category for some...
  30. D

    I HHL Algorithm for Solving Linear Equations

    I have a question about HHL algorithm https://arxiv.org/pdf/0811.3171.pdf for solving linear equations of the form: A x = b Where A, x and b are matrices Take for example 4x1 + 2x2 =14 5x1 + 3x2 = 19 HHL apply the momentum operator eiAτto/T on the state, do a Fourier Transform on |b> and...
  31. meyol99

    A Atomic state that is a coherent superposition?

    Can someone explain the meaning of the k vector and the general meaning of this equation?
  32. G

    2D subspace of a Hilbert space

    Homework Statement Have to read a paper and somewhere along the line it claims that for any distinct ## \ket{\phi_{0}}## and ##\ket{\phi_{1}}## we can choose a basis s.t. ## \ket{\phi_{0}}= \cos\frac{\theta}{2}\ket{0} + \sin\frac{\theta}{2}\ket{1}, \hspace{0.5cm} \ket{\phi_{1}}=...
  33. D

    Finding the magnetization in nuclear magnetic resonance

    Homework Statement J-coupling term between two spins is HJ = ħJ/4 σz(1) σz(2) In the measured magnetization spectrum of the spins, this leads to the splitting of the individual spin lines by frequency J, which we’ll now derive. We can write the magnetization of spin 1 as: <M1(t)> =...
  34. DrHix

    How do I construct a controlled Hadamard gate?

    Homework Statement I am supposed to construct a controlled Hadamard gate using only single qubit and CNOT gates. Homework Equations [/B] We know that any arbitrary unitary Operator U can be written as the Martrix product U=AXBXC, where X is the NOT-Matrix and ABC=1 (identity matrix) I've...
  35. J

    A Shor's algorithm and similar exploitation of QM?

    Shor's algorithm is rather the most interesting quantum algorithm as it shifts a problem which is believed to need exponential classical time, to polynomial time for quantum computer, additionally endangering asymmetric encryption like RSA and ECC. The real question is if there are other...
  36. C

    A Generalizing distinguishability of photons on HOM dip?

    Hello all. I am trying to determine what is the effect of having photons that are distinguishable undergoing a quantum interference process. To do that, I try to generalize the Hong-Ou-Mandel effect, and try to determine what are the terms that appear as a function of the product of the creation...
  37. Johny Boy

    A Using feedback in quantum measurements

    If we consider an efficient measurement performed on a system in a pure state. How would we use feedback (by applying to the system a unitary operator that depends upon the measurement result), to prepare the system in the same final state for every outcome of the measurement (this can be done...
  38. E

    Other Better Supervisor or preferred field?

    I am attempting to choose a field of study for my masters course following my undergraduate course however due to the circumstances of the researchers I have to choose between a better supervisor or a preferred field of study; my ideal field would be theoretical quantum computing, however the...
  39. S

    I Why is entanglement crucial for quantum computing?

    Hello I understand what entanglement is and also what superposition is. But I don't understand why qbits in a quantum computer must be entangled.
  40. D

    I They physics of phase inversion in Grover's algorithm

    How would this operator be implemented physically if we had a quantum computer? In Grover's algorithm this magical operator is often called "phase inversion". Here is the operator from wiki: https://wikimedia.org/api/rest_v1/media/math/render/svg/07fb23bffa787430b084971c6a108a8f6ff6c2b3 It’s...
  41. Auto-Didact

    A Decoherence-free phononic BEC quantum devices?

    Howl et al. 2016, Quantum Decoherence of Phonons in Bose-Einstein Condensates Anyone in the field of quantum information/quantum computation wish to comment on such an approach for building a quantum computer?
  42. munirah

    How to differentiate GHZ state and W state?

    Good day, I try to differentiate GHZ-state and W-state using three tangle. Suppose The value three tangle for GHZ-state equal to 1 while W-state equal to 0. I used three tangle formula, $$\tau_{ABC}=\tau_{A(BC)}-\tau_{AB}-\tau_{AC}=2(\lambda^{AB}.\lambda^{AB}+\lambda^{AC}.\lambda^{AC})$$...
  43. munirah

    How can I make singular matrix become nonsingular matrix?

    << Mentor Note -- thread moved from Homework Help forums to General Math >> Good day, I run coding in Mathematica. But, I get singular matrix A at certain loop. In theory, how can I make matrix A become orthogonal A=\begin{pmatrix} 0& 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0& 0 & 0 & 0 & 0 & 0 & 0 &...
  44. munirah

    Understanding the Parameters of SU(4) and SU(2)

    Homework Statement Good day, From my reading, SU(4) have 15 parameter and SU(2) has 3 paramater that range differently with certain parameter(rotation angle). And all the parameter is linearly independent to each other. My question are: 1. What the characteristic of each of the parameter? 2...
  45. A

    Programs Where can I do a masters in Quantum Mechanics?

    I am an undergraduate student in India doing my final year BS degree in Math. I am extremely interested in quantum mechanics and want to peruse quantum computation. What is the best possible course that I can take for my Masters? There appears to be a limited number of colleges that offer a...
  46. polyChron

    Rotations in Bloch Sphere about an arbitrary axis

    Hey, (I have already asked the question at http://physics.stackexchange.com/questions/244586/bloch-sphere-interpretation-of-rotations, I am not sure this forum's etiquette allows that!) I am trying to understand the following statement. "Suppose a single qubit has a state represented by the...
  47. youssef99

    Schools How can I pursue a career in quantum computing through college?

    Hello I have recently taken interest in physics and mostly Quantum computing and i was wondering what is the best way of tackling that field . Is it to have a major in Computer Science and possibly a major/minor in physics? or to aim for colleges that have specific classes of quantum...
  48. V

    Recovering QM from QFT: David Tong Notes

    Reading through David Tong lecture notes on QFT.On pages 43-44, he recovers QM from QFT. See below link: [QFT notes by Tong][1] [1]: http://www.damtp.cam.ac.uk/user/tong/qft/qft.pdfFirst the momentum and position operators are defined in terms of "integrals" and after considering states that...
  49. S

    Quantum Computing and Math prequisities

    Hello, I am a Physics undergraduate, currently beginning my third (out of four) year of studies. I have already taken courses about Real and Complex Analysis, Linear Algebra, ODEs and PDEs (for Maths), Classical Mechanics (Lagrangian and Hamiltonian formalism), Electromagnetism, Special...
  50. EJC

    Suggestions for Quantum Computation Ph.D Program?

    I am going to be applying to grad schools in the coming months, and plan to apply to many schools. I'm looking for programs in quantum computation, quantum information, quantum optics, etc... (related research often falls under many different names). These programs generally are categorized in...