PAR Class 20, Thu 2019-03-28

Source

2   Quantum computing

  1. https://www.quantum-inspire.com/kbase/introduction-to-quantum-computing/

  2. More from

    Quantum Computing for Computer Scientists 1st Edition ( recommended in Microsoft talk)

    1. Compare byte with qbyte.

    2. State of byte is 8 bits.

    3. State of qbyte is 256 complex weights.

    4. They all get modified by each operation (aka matrix multiply).

    5. That is the power of quantum computing.

    6. The current limitations are that IBM does only a few qbits and that the operation is noisy.

    7. No cloning: Cannot copy a qbit, but can move it.

    8. Copied from page 171: All quantum algorithms work with the following basic framework:

      1. The system will start with the qubits in a particular classical state.
      2. From there the system is put into a superposition of many states.
      3. This is followed by acting on this superposition with several unitary operations.
      4. And finally, a measurement of the qubits.

    9. Ways to look at measurement:

      1. Converts qbit to classical bit.
      2. Is an interaction with the external world.
      3. Information is not lost, but leaks into the external world.
      4. Is an operator represented by a matrix.
      5. that is Hermitian, i.e., it's equal to its complex transpose.
      6. For physical systems, some operators compute the system's momentum, position, or energy.
      7. The matrix's eigenvalues are real.
      8. The result of the operation is one of the eigenvalues.

    10. https://en.m.wikipedia.org/wiki/Bloch_sphere:

      1. The state of a qbit can be represented as a point on or in a sphere of radius 1.
      2. E.g., |1> is the north pole, |0> the south pole.
      3. Many operations are rotations.

    11. Common operations (aka gates):

      https://en.wikipedia.org/wiki/Quantum_logic_gate

      1. Hadamard.

        Creates a superposition.

        https://cs.stackexchange.com/questions/63859/intuition-behind-the-hadamard-gate

      2. Toffoli, aka CCNOT.

        Universal for classical boolean functions.

        (a,b,c) -> (a,b, c xor (a and b))

        https://en.wikipedia.org/wiki/Toffoli_gate

      3. Fredkin, aka CSWAP.

        https://en.wikipedia.org/wiki/Fredkin_gate

        3 inputs. Swaps last 2 if first is true.

        sample app: 5 gates make a 3-bit full adder.

  3. Algorithms:

    1. Some, but not all, are faster.
    2. Bounded-error quantum polynomial time (BQP)
      1. "is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances" - https://en.wikipedia.org/wiki/BQP
      2. Includes integer factorization and discrete log.
      3. Relation to NP is unknown (big unsolved problem).
    3. Grover's algorithm:
      1. https://en.wikipedia.org/wiki/Grover%27s_algorithm
      2. Given a black box with N inputs and 1 output.
      3. Exactly one input makes the output 1.
      4. Problem: which one?
      5. Classical solution: Try each input, T=N.
      6. Quantum: $T=\sqrt(N)$.
      7. Probabilistic.
      8. Apps: mean, median, reverse a crypto hash, find collisions, generate false blocks.
      9. Can extend to quantum partial search.
      10. Grover's algorithm is optimal.
      11. This suggests that NP is not in BQP .
    4. Shor's algorithm:
      1. Factorize an int.
      2. in BQP.
      3. almost exponentially faster than best classical algorithm.
      4. Largest examples I can find:
        1. 56153 = 233 × 241.
        2. https://medium.com/@aditya.yadav/rsa-2048-cracked-using-shors-algorithm-on-a-quantum-computer-660cb2297a95

  4. https://quantumexperience.ng.bluemix.net/qx/tutorial ctd.