Shor's Algorithm - polynomial-time quantum algorithm for factoring

# CS 6520 - Computational Complexity Fall 2017

## Saturday, November 18, 2017

## Wednesday, November 15, 2017

### Day 34

More quantum: Deutsch-Jozsa, Grover and Simon

- Rapid solution of problems by quantum computation by David Deutsch and Richard Jozsa
- A fast quantum mechanical algorithm for database search by Lov Grover
- On the Power of Quantum Computation by Dan Simon

## Monday, November 13, 2017

### Day 33

Introduction to Quantum Computing. Gave the matrix definition of quantum machines (see my paper below) and described the Hadamard matrix and its properties.

- One complexity theorist's view of quantum computing by Lance Fortnow

## Friday, November 10, 2017

### Day 32

In this class we showed how MIP = NEXP implies lower bounds on approximating the clique problem and how this led to the PCP theorem. The PCP theorem states that every language in NP has probabilistically checkable proof where the verifier uses O(log n) random bits and makes only a constant number of queries to a proof that just returns bit. Here is a strong version.

For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

For any constant α > 7/8, there is a polynomial-time computable function f mapping 3-CNFs to 3-CNFs such that for all formula φ,

- If φ is satisfiable then f(φ) is satisfiable.
- If φ is not satisfiable then every assignment to f(φ) satisfies at most an α-fraction of the clauses.

The proof is an assignment, O(log n) random coins are used to pick a clause and only the 3-queries to the variables of that clause are needed.

We also talked about the Unique Games conjecture.

Links:

- Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra and Mario Szegedy
- Proof verification and the hardness of approximation problems by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy. First proof of the PCP theorem.
- The PCP theorem by gap amplification by Irit Dinur. A simpler more combinatorial proof of the PCP theorem.
- Some optimal inapproximability results by Johan Håstad. Gets the tight result for 3-SAT above.
- On the power of unique 2-prover 1-round games by Subhash Khot. This paper introduces unique games.
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell
- Compendium of NP Optimization Problems. Good list of problems and their best known approximations and limitations.

## Wednesday, November 8, 2017

### Day 31

Assignment 3 has been graded and solutions posted on the T-Square resource page. Assignment 4 has been posted and is due November 20.

We showed that MIP (in PCP form) was equal to NEXP.

We showed that MIP (in PCP form) was equal to NEXP.

- Non-deterministic exponential time has two-prover interactive protocols by László Babai, Lance Fortnow and Carsten Lund
- Robust Characterizations of Polynomials with Applications to Program Testing by Ronitt Rubinfeld and Madhu Sudan. This is a more direct and robust low-degree test.

## Monday, November 6, 2017

### Day 30

We showed that IP = PSPACE via the Shen proof and introduced the MIP model.

- IP = PSPACE by Adi Shamir
- IP =PSPACE: Simplified proof by Alexander Shen
- On the power of multi-prover interactive protocols by Lance Fortnow, John Rompel and Michael Sipser

## Friday, November 3, 2017

### Day 29

We gave the proof that co-NP and P

^{#P}have interactive protocols (Arthur-Merlin games with unbounded rounds). We will generalize to PSPACE on Monday.- Algebraic methods for interactive proof systems by Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan

Subscribe to:
Posts (Atom)