Quantum computing Definition and 140 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. Azerack

    Admissions Safety School Programs for a Physics PhD

    Hi, this is my first time using the Physics Forums so please let me know if this question belongs somewhere else. I'm a senior undergraduate at a mid-size institution in the United States seeking to purse a PhD in High Energy Theoretical physics or Quantum Information/Computing. I'm aware these...
  2. Bob Walance

    Insights Quantum Computing for Beginners

    revisions for the attached PDF: r3 - Changed all occurrences of the word 'conventional' to 'classical'. Headings are no longer all capital letters. r2 - Fixed a couple of spelling and grammar errors.
  3. F

    Calculators Repositories of Quantum Computing projects?

    Hello. I need to code a project (solution of a typical problem or approaches to new one) of quantum computation and I want to study any solved project in order to understand the algorithms and how to run the script in a real quantum computer or simulator. Where can I found some repositories of...
  4. Admiralibr123

    Physics Quantum Computing masters with Theoretical physics background

    I want to do a masters related to quantum computing from a physics background and my criteria for the place is: 1. A quantum computing group with experimental realizations and industrial ties. 2. A strong theoretical physics department with research in fundamental physics 3. A good chance of...
  5. Bob Walance

    B A homebrew quantum computer simulator

    A while ago I started writing a quantum computer simulator in order to learn more about quantum computing. It certainly has helped me. The simulator is written in Python and the development was done on a Raspberry Pi 4. It has also been tested on a pc. In order to see it do something useful I...
  6. P

    I Quantum phase estimation - Question regarding rewriting the state

    In Nielsen and Chuang p.223 we have the following situation: $$\frac{1}{2^t} \sum\limits_{k,l=0}^{2^t-1} e^{\frac{-2\pi i k l}{2^t}} e^{2 \pi i \varphi k} |l\rangle$$ Which results from applying the inverse quantum Fourier transform to state ##\frac{1}{2^{t/2}} \sum\limits_{k=0}^{2^t-1}...
  7. S

    Nobel prize in physics for quantum cryptography?

    Is it likely that this year's Nobel prize could be awarded to the field of quantum cryptography with Charles H Bennet, Gilles Brassard and Artur Ekert as possible nobel laureate candidates?
  8. Vatsy31

    Admissions Can someone critique my statement of purpose? (Master's Degree in Quantum Engineering)

    I have written and rewritten a lot of times but I need some fresh eyes on my sop. It would be great if someone can help me out. I have less than a week to readjust it and send. My motivation to apply for the Masters Degree in quantum engineering at University of Wurzburg is to...
  9. 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...
  10. E

    Measurements of GHZ state

    Here's what I think I understand: First off, the GHZ state ##|GHZ \rangle = \frac {|000\rangle+|111\rangle} {\sqrt 2}##, and ##\sigma_x## and ##\sigma_y## are the usual Pauli matrices, so the four operators are easy to calculate in Matlab. I'm thinking the expectation values of each operator...
  11. E

    Constructing the GHZ state

    I know |GHZ>=(1/sqrt(2))[1; 0; 0; 0; 0; 0; 0; 1], and |000>= the tensor product |0> x |0> x |0> = [1; 0; 0; 0; 0; 0; 0; 0]. Can I apply single qubit gates (i.e. 2x2 matrices) and CNOT (a 4x4 matrix) to 8x1 column vectors? If so, does anyone know a good starting point or a hint to get me moving...
  12. E

    Controlled-Z gate as a product of exponentials

    I have numerous points of confusion: what does it mean that the matrices are within the exponential? How do I go about doing the matrix multiplication to prove the given form of CZ matches the common form, the 4x4 matrix? Update: using the fact that exp(At)=∑ ((t^n)/n!)*A^n, where A is a...
  13. E

    Projective measurements of quantum processor

    Am I correct in thinking that the system measures the probability |<f|1>|^2 for some state <f|? Then the probabilities for each of the six states would be: |<0|1>|^2= 0 |<1|1>|^2= 1 |<+x|1>|^2= |(1/√2)|^2 = 1/2 |<-x|1>|^2= |(-1/√2)|^2 = 1/2 |<+y|1>|^2= |(-i/√2)|^2 = 1/2 |<-y|1>|^2= |(i/√2)|^2...
  14. E

    Qubit Operations

    Part a: Gate H X Y Z S T R_x R_y Theta pi pi pi pi pi/2 pi/4 pi/2 pi/2 n_alpha (1/sqrt(2))*(1,0,1) (1,0,0) (0,1,0) (0,0,1) (0,0,1) (0,0,1) (1,0,0) (0,1,0) Using the info from the table and equation 1, I find: U_H=(i/sqrt(2))*[1,1;1,-1] U_X=i*[0,1;1,0] U_Y=i*[0,-i;i,0] U_Z=i*[1,0;0,-1]...
  15. Quantum computing & chill

    Quantum computing & chill

    A thing doing its own thingy thing could compute faster than a computer can compute.
  16. M

    A Tensor and vector product for Quantum

    Hello, I am calculating the krauss operators to find the new density matrix after the interaction between environment and the qubit. My question is: Is there an operational order between matrix multiplication and tensor product? Because apparently author is first applying I on |0> and X on |0>...
  17. F

    A Random Quantum Walk

    I am an undergraduate doing research on QC/QI. My current topic to learn is continuous-time quantum walks, but first I must learn the random quantum walk. That being said, I was wondering if someone could simply explain what a random quantum walk is and then explain how they could be useful with...
  18. Q

    I "Basic" question about Grover's Quantum Computing algorithm

    Hi everyone, I'm a computer scientist (not a physicist), so I will ask a computer scientist's question. In all the descriptions I found of Grover's algorithm, there is an element that is puzzling the computer scientist in me: it seems that you need to tell the Oracle about the position of the...
  19. R

    Can random, unguided processes produce a rational brain?

    I am fascinated by Einstein’s quote that the most unbelievable aspect of the universe was that it was intelligible. So my question is does anyone know whether it is so unlikely as to be absurd to suppose that random unguided processes could produce a rational brain in man in as little as 3...
  20. F

    A How to measure the first qubit in two qubit system? QC

    I was wondering how to measure the first or even the second qubit in a quantum computing system after for example a Hadamard Gate is applied to the system of these qubits: A|00>+B|01>+C|10>+D|11>? A mathematical and intuitive explanation would be nice, I am a undergraduate sophomore student...
  21. D

    I Oracle questions in Grover's Algorithm

    Following these links: https://people.cs.umass.edu/~strubell/doc/quantum_tutorial.pdf https://www.codeproject.com/Articles/1131573/Grovers-Search-Algorithm-explained I have these questions: The Oracle "knows" the correct bits in the first invocation itself. So why do sqrt(N) invocations where...
  22. E

    I Clarification on what we can consider a qubit to be

    In a 2 level quantum system, should I consider the states |0> and |1|> to be qubits by themselves? Or is only the SUPERPOSITION of these two states, \alpha |0> + \beta |1> considered to be a qubit?
  23. E

    I Quantum Computing and Superposition of states

    I'm watching a lecture on the intro to quantum computing. See the attached image which will be useful as I describe my question. So the professor says that we have this single photon and it's in this state, ## | 0 > ##. He states that when we send this photon through a beam splitter that it...
  24. D

    What is Leakage in terms of quantum computing?

    I am doing a project on stabilizer code, and I keep running into a term about qubits and leakage. What does leakage mean?
  25. R

    I Does 'Phase Inversion' grow exponentially?

    Hi! So I'm studying Gover's Algorithm and I have this doubt: Does 'Phase inversion gate' grows exponentially? I mean, if I want to signal the one combination that is the answer, I must be able to represent all 2^N states, where N is the number of qubits in the system. How do I do this without...
  26. J

    A Shor's algorithm - need to uncompute auxiliary qubits?

    Due to required reversibility, classical function (f(a)=y^a \mod N) in Shor's algorithm needs a lot of auxiliary qubits. I was afraid that their later treatment might influence the computation - and just got confirmation from Peter Shor himself: that we need to "uncompute" these auxiliary...
  27. J

    New member thread (Interested in Quantum Computing, AI)

    Hey all, I'm a student in university who wants to Double Major in Computer Engineering and Physics or Mathematics. Ideally I want to get some time in working on quantum computers and some time in working on advanced AI, so one of the big things I want to do is pick the community's brain on...
  28. Q

    Physics Orienting myself toward quantum computing or a related field

    I am well aware that QC-related graduate programs are competitive so I am preparing myself for a rejection. Not because I'm unconfident. But because everyone should have a backup plan just in case. I haven't applied yet because I'm about to take the GRE. I really do enjoy both quantum physics...
  29. C

    A Simple way to create entangled photon pairs?

    Two photons arrive at a hypothetical 50:50 Beam-Splitter with no phase shift between reflected and transmitted modes. One enters the Left side and the other the Bottom side of the BS as shown in Fig.1 of the link below: https://drive.google.com/open?id=0B5JsDLKoUSA5emk5Qk9nUHVIelE Each photon...
  30. R

    I Arithmetic Block in Shor Algorithm

    Hello everyone! So I was looking at Shor Algorithm for prime factorization and I have some doubts in the arithmetic part. Let's define a function f that : f(x) = ax mod N. The middle step in shor algorithm is to calculate, simultaneously, all values of f. In some papers and books, I saw some...
  31. S

    A What's the best quantum simulator?

    Hello. What is the best quantum simulator till now? We could select two categories: a) Best full simulator able to solve the equations describing a system in 3D and watching its temporal evolution. b) Best digital simulator, algorithm analyzer. For the second options I have some candidates...
  32. S

    Books on quantum computing?

    Hello. What is a good book to learn Quantum Computing? I've being looking for the most common ones and reading some reviews at Amazon, and created this list: A Short Introduction to Quantum Information and Quantum Computation, Le Bellac, 2006 An Introduction to Quantum Computing Algorithms...
  33. Q

    Physics Simulation and model science or quantum computing

    I am a computer science under graduate,I am more interested in scientific research, so I am preparing to enrol myself masters in quantum computing or simulation sciences. before i join i want to research what are the scope and job opportunities are available for simulation sciences(like...
  34. victor94

    I Help in understanding a quantum circuit

    I'm in a proyect to simulate quantum circuits in robots like in this paper ( http://ieeexplore.ieee.org/document/4215941/ ) ,the first thing that i need to do is to simulated the circuit that is in that paper: But i'm having trouble understanding how the hadamard gate affects the "C"...
  35. Luis Obis

    Programs Choosing a Master's degree in Physics

    I am a physics student from Spain and hopefully I will be finishing my degree in physics (4y) by next June. I am trying to decide on a Master's program to study but I am finding very difficult to decide since there are so many oportunities and so diverse specially when looking for programs...
  36. A

    I Simon's Algorithm

    Hi all, I am sure some of you have heard of Simon's algorithm that calculates a secret string s when given a black box. Basically, let's say we have a qubit x that is n digits long. Now the black box contains a function f that outputs f(x+s) where s is the mystery string and + is bit-wise modulo...
  37. munirah

    I How reduced density matrix obtained from the matrix.

    Can any expert help me in explaining how this example below get the reduced density matrix from the density matrix in bipartite system. $$\rho =\frac{1}{4}\begin{pmatrix} 1 & 1 & cos(\frac{\alpha}{2})-sin(\frac{\alpha}{2}) & cos(\frac{\alpha}{2})+sin(\frac{\alpha}{2}) \\ 1 & 1 &...
  38. Abhishek Sethi

    Research in Quantum Computing

    Hi, I am an undergraduate student from India. Pursuing double major in Physics and Mechanical Engineering. I have completed 4 semesters(2 years) of my college. I had taken a class titled "Quantum information and computing" and it interested me a lot. I really love math and computations...
  39. S

    Quantum Computing

    Hello, Am an undergraduate student of physics(hons) and want to work on Quantum Computing in future. Can anybody please suggest how I should go about it? Thanks in advance
  40. Domenico94

    A What is quantum computing research mostly focused on?

    What is quantum computing research mostly focused on? I mean, is it mostly about a physical point of view ( Like building better quantum transistor, or better quantum diodes, or, for example, using entalgment effect, to achieve better purposes), or is it mostly focused with quantum architectures...
  41. JakesDev96

    Is quantum programming really possible?

    Hello all, I have come here to gather what the communities view is on the possibility of quantum computing in relation to the actual logic behind synchronous programming and the laws that (seem to) govern the quantum realm. Coming from a background in computer science, I have studied the basic...
  42. EJC

    Schools Chances of Getting Into Graduate School Ph.D Programs

    I am a rising senior at a small liberal arts college, with an incredibly small (and therefore unrecognized) physics program. I am seeking advice regarding which Ph.D programs are within my reach. I plan on applying to AMO (Atomic, Molecular, and Optics) Ph.D programs with the intention of...
  43. A

    Measuring a qbit

    I am newly learning quantum computing and am confused about some concepts. Suppose your qbit is the electron of a hydrogen atom and its in the state α|0> + β|1> . As far as I can understand, this means that if you measure the qbit in |0>, |1> basis, you will get a ground state electron with the...
  44. A

    Physics Career in quantum computing

    Hi. I am an undergraduate physics student and I really like the field of quantum computing. Can someone please tell me how good are the opportunities to work and research in this field? As I understand, there are not many places that do research in quantum computers as compared to something like...
  45. ant0n

    How would observation of the state of qubits affect them?

    Firstly, I apologise for any lack of understanding, incorrect assumptions or misinterpretations of the very little I know about physics, quantum mechanics & quantum computing. I am not an academic, scientist or mathematician, but a software engineer with an interest in quantum computing and...
  46. C

    What is trivial and non-trivial gate in computing?

    My question seems like it should be posted in Computer Engineering section, but below is how I found this word. I was reading the textbook: Quantum Computation And Quantum Information - by Michael A. Nielsen and Issac L. Chuang. and I came across with the this word; "1.3.1 Single qubit gates...
  47. M

    Topology required for topological quantum computing?

    I guess the usual answer would be to learn as much as possible. Some background about me: I am not a physicist but I'd like to pursue a PhD in theoretical physics (after a year or two) and work on topological quantum computing. I am familiar with quantum mechanics and solid state physics (at...
  48. AdityaDev

    Data storage in an SSD

    I am still in high school but my curiosity is not stopping me from posting in this forum. How is data stored in SSD? How does it differ from the old HDD? I heard that atoms are used to store data. How? Binary consists of 0 and 1. How does someone use an atom to represent 0 and 1? Does positive...
  49. P

    Help with classes to get into Quantum Computing

    Hi I am an undergrad student in an Electrical engineering program and going for my masters and undergrad degree at the same time (special program i am in). I an very interested on the hardware side of quantum computing as to have a future career in this field (eventually will go for a PhD). I...
  50. J

    Physics Masters in computer science (A.I) or masters in theoretical physics for career in quantum computatio

    I'm currently in my final year of BSc(Hons) in mathematics and computer science & A.I (applied math stream). Indeed, I'm starting to think about what masters I want to pursue and the kind of subject I would like to specialize in. I am really interested in quantum computation and the prospects of...