Editing Quantum logic gate (section)

=== Measurement on registers with pairwise entangled qubits ===
[[File:The_effect_of_unitary_transforms_on_registers_with_pairwise_entangled_qubits.png|thumb|upright=1.8|right|The effect of a unitary transform F on a register A that is in a superposition of <math>2^n</math> states and pairwise entangled with the register B. Here, {{mvar|n}} is 3 (each register has 3 qubits).]]
Take a [[Quantum register|register]] A with {{mvar|n}} qubits all initialized to {{nowrap|<math>|0\rangle</math>,}} and feed it through a [[#Hadamard transform|parallel Hadamard gate]] {{nowrap|<math display="inline">H^{\otimes n}</math>.}} Register A will then enter the state <math display="inline">\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^{n}-1} |k\rangle</math> that have equal probability of when measured to be in any of its <math>2^n</math> possible states; <math>|0\rangle</math> to {{nowrap|<math>|2^n-1\rangle</math>.}} Take a second register B, also with {{mvar|n}} qubits initialized to <math>|0\rangle</math> and pairwise [[#CNOT|CNOT]] its qubits with the qubits in register A, such that for each {{mvar|p}} the qubits <math>A_{p}</math> and <math>B_{p}</math> forms the state {{nowrap|<math>|A_{p}B_{p}\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}</math>.}}

If we now measure the qubits in register A, then register B will be found to contain the same value as A. If we however instead apply a quantum logic gate {{mvar|F}} on A and then measure, then {{nowrap|<math>|A\rangle = F|B\rangle \iff F^\dagger|A\rangle = |B\rangle</math>,}} where <math>F^\dagger</math> is the [[Unitary matrix|unitary inverse]] of {{mvar|F}}.

Because of how [[#Unitary inversion of gates|unitary inverses of gates]] act, {{nowrap|<math>F^\dagger |A\rangle = F^{-1}(|A\rangle) = |B\rangle</math>.}} For example, say <math>F(x)=x+3 \pmod{2^n}</math>, then {{nowrap|<math>|B\rangle = |A - 3 \pmod{2^n}\rangle</math>.}}

The equality will hold no matter in which order measurement is performed (on the registers A or B), assuming that {{mvar|F}} has run to completion. Measurement can even be randomly and concurrently interleaved qubit by qubit, since the measurements assignment of one qubit will limit the possible value-space from the other entangled qubits.

Even though the equalities holds, the probabilities for measuring the possible outcomes may change as a result of applying {{mvar|F}}, as may be the intent in a quantum search algorithm.

This effect of value-sharing via entanglement is used in [[Shor's algorithm]], [[Quantum phase estimation|phase estimation]] and in [[Quantum counting algorithm|quantum counting]]. Using the [[Quantum Fourier transform|Fourier transform]] to amplify the probability amplitudes of the solution states for some [[Computational problem|problem]] is a generic method known as "[[Quantum algorithm#Fourier fishing and Fourier checking|Fourier fishing]]".<ref>{{Cite arXiv|last = Aaronson|first = Scott|year = 2009|title=BQP and the Polynomial Hierarchy|class=quant-ph|eprint=0910.4698}}</ref>