Quantum Computing Concepts
Concepts
vs. classical computing, challenges on problems with exponential scaling characteristics (many variables, many paths)
Qubit: smallest unit of information measurement in quantum computing, main difference vs. classical bit: classical bit takes on one of two possible values: 0 or 1, while qubit can represent both 0 and 1 simultaneously. N qubits can represent 2 power (N) states. Key properties of qubits are superposition, entanglement.
superposition: Qubits can represent multiple combinations of 0 and 1 at the same time, which process a vast amount of information concurrently.
entanglement: correlate multiple qubits so we can change their states simultaneously, meaning computing in parallel. A typical entangled state, called a Bell state (other common states, GHZ state, W state), is:
quantum state: represents the state of a quantum system, such as a qubit (quantum bit). For a single qubit, the quantum state can be written in Dirac notation as:
∣ψ⟩=α∣0⟩+β∣1⟩
4 Bell states, 2, 3
- ∣Φ+⟩=1/sqrt(2)*(∣00⟩+∣11⟩)
Start with the initial state ∣00⟩. Apply a Hadamard gate (H) to the first qubit:H∣0⟩=1/sqrt(2)(∣0⟩+∣1⟩). State becomes:1/sqrt(2)(∣00⟩+∣10⟩). Apply a CNOT gate with the first qubit as the control and the second as the target - ∣Φ−⟩=1/sqrt(2)*(∣00⟩−∣11⟩)
Create ∣Φ+⟩, then apply Z gate (Z) to the first qubit - ∣Ψ+⟩=1/sqrt(2)*(∣01⟩+∣10⟩)
Create ∣Φ+⟩. Apply an X gate to the second qubit - ∣Ψ−⟩=1/sqrt(2)*(∣01⟩−∣10⟩)
Create ∣Ψ+⟩. Apply a Z gate to the first qubit
quantum state vector: a mathematical object that represents the state of a quantum system. It is a vector (typically expressed as a column vector) in a complex vector space called Hilbert space.
gates: basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits. Some common single-qubit gates are X, Y, Z gates.
measurement: capture collapsed/definite state of qubit
standard basis measurement: when a system in a quantum state is measured, the observer performing the measurement won’t see a quantum state vector, but rather some classical state. In this sense, measurements act as the interface between quantum and classical information, through which classical information is extracted from quantum states. If a quantum state is measured, each classical state of the system results with probability equal to the absolute value squared of the entry in the quantum state vector corresponding to that classical state. This is known as the Born rule in quantum mechanics. A 1-qubit system, in general, can be in a state 𝑎|0⟩+𝑏|1⟩ where |0⟩ and |1⟩ are basis vectors of a two dimensional complex vector space. The standard basis for measurement here is {|0⟩,|1⟩}.
Other basis measurement: measurement in z (computational), y (circular) and x (Hadamard) bases. (Intuitively, think you can ask different questions: e.g. is it in 0 or 1? is it spinning pointing up or down? are the two qubits entangled?)
reversible transformations: input can be reconstructed from output after series of transformations. Reversibility is a special property of quantum operations. It isn’t always inherent in classical operations.
bloch sphere: a unit 2-sphere, with antipodal points corresponding to a pair of mutually orthogonal state vectors. The north and south poles of the Bloch sphere are typically chosen to correspond to the standard basis vectors |0⟩ and |1⟩, respectively, which in turn might correspond e.g. to the spin-up and spin-down states of an electron.
interference: when we measure state, it will collapse to one answer. Interference is used to amplify correct solutions and cancel out incorrect ones, optimizing the search process.
phase: The “angle” of the complex number in the superposition; it determines how quantum states interfere with each other. (complex number: polar form of a complex number is z=r(cos θ+i sin θ) where r and θ are real (r=sqrt(a^2+b^2), θ (also called the phase) is the angle the complex number makes with the positive real axis. It can be found using the arctangent function:
). The exponential form of a complex number is z=r^eiθ where r and θ are real.)
- Constructive interference occurs when the phases align (i.e., the relative phase is 00 or an integer multiple of 2π), increasing the probability of certain outcomes.
- Destructive interference occurs when the phases differ by π (or odd multiples), leading to cancellation and reducing the probability of certain outcomes.
A single qubit can be described by wavefunction, and entangled qubits can be described by overall wavefunction. Interference can change probability distribution of the states (constructive interference to increase probability of correct answer, destructive interference to decrease probability of incorrect answer. When you measure, correct answer will come out).
Shor algorithm: log(N) complexity vs. 2 power (N) complexity for classical algorithm
Grover’s algorithm: square (N) vs N for classical algorithm
Challenges of quantum computing: decoherence (want qubits to entangle to each other, but not to the environment), scalability (noise factors increase as number of qubits increase)
Quantum computing still in very early stage. Solving climate change, factoring big primes in cryptography need big enough quantum computer, which is not in a short-term vision (5 years).
Impact
Cybersecurity: signature hacking (which is trust base for online communication)
quantum encryption vs. online encryption
Walked through Shor’s algorithm to factor N: the key part is that one step is to find some frequency, and this step can be parallelized by superposition and Fourier transforms can be used to find frequency. Briefly described lattice-based post-quantum cryptography, 2.
Computing model
quantum annealing: solving optimization problems by encoding the problem into the energy levels of a physical system and then letting the system evolve towards the global minimum of the energy landscape.
gate-based: performing quantum computation by applying a sequence of quantum gates to a set of qubits.
Quantum annealing is considered to be relatively robust against certain types of errors, such as noise and decoherence. In contrast, gate-based quantum computing is more sensitive.
General use cases
Pharmaceuticals: make drug design, and toxicity testing less dependent on trial and error and more efficient
Chemicals: improve catalyst designs
Automotive: product design, supply-chain management, production, and mobility and traffic management
Finance: portfolio and risk management
- Optimization: large autonomous fleets optimization, Grid optimization, Weather forecasting, Risk analysis, Portfolio optimization, Fraud detection, Product pricing and insurance underwriting, Route and traffic optimization, Supply chain and inventory optimization, Design optimization, Drug interaction prediction, Personalized medicine taking into account genomics
- Research: Material science, Drug research
- Cryptography/espionage
- Industry specific applications: chemical material production
- Quantum simulation: search materials interaction for superconductivity more quickly, catalyst
Appendix
Quantum mechanics: particle dynamics described by waves of probability, reality embraces many states simultaneously, new kind of probabilities (not just positive), quantum waves can interfere, measurement collapses probability wave
Basic quantum computing concepts
https://arxiv.org/vc/quant-ph/papers/0511/0511061v1.pdf
https://people.maths.bris.ac.uk/~csxam/presentations/ucastalk.pdf
https://cs.lbl.gov/assets/CSSSP-Slides/20190624-deJong.pdf
GPT tutor
In addition to other learning resources, we can also leverage GPT tutor to provide a systematic guide for basic quantum computing concepts.
