# Quantum computing ## Fundamental concepts ### Qubits #### Logical vs physical qubits A logical qubit is the abstract "pure" version of a qubit that has the correct probability distribution. Physical qubits have errors. Ensembles of physical qubits can simulate a logical qubit via error-correction mechanisms. It is currently estimated that 1000 physical qubits would be needed to simulate 1 logical qubit. ### Quantum computation A quantum computation takes a vector of all possible states of the system - if there are $n$ qubits, a vector of $2^{n}$ states, and manipulates it into another vector. These vectors are also called *superpositions*. So the computation takes the system from one superposition state, to another. To actually get an output, a measurement needs to be made, which **collapses** the superposition to a single state. **We are not able to access the entire output vector all at once.** With the output vector, there is an associated *probability distribution* that determines the probability that the system will collapse to a given state. Part of the role of a quantum algorithm is to manipulate also this probability distribution, and make it concentrate on a single value. If it can be done, then with very high probability the measurement will produce the desired result of the computation. Thus quantum computations are particularly useful in cases where *finding* the answer is very hard, but *verifying* the answer is easy (like Sudoku, or prime factoring). ## Abilities of quantum computing [[Shor's algorithm]] describes how, in theory, quantum computers could factor incredibly large numbers efficiently. This means that Shor's algorithm could be the downfall of [[RSA]] cryptography. [[Grover's algorithm]] gives an improvement in finding the correct solution for problems that in general would require going over all possible solutions until the correct is found. ## Quantum computing and cryptography **Post-quantum cryptography**, also known as quantum-proof cryptography, aims to create encryption methods that cannot be broken by algorithms, or calculations, that run on future quantum computers. **Quantum cryptography** uses the laws of quantum physics to transmit private information in a way that makes undetected eavesdropping impossible. ## Links - [How Will Quantum Technologies Change Cryptography?](https://scienceexchange.caltech.edu/topics/quantum-science-explained/quantum-cryptography)