Sequential MPS encoding

[ACE07-Sev]

1. How the technique works

Sequential MPS encoding [1] is a way to approximately encode a matrix product state up to arbitrary fidelity in $O(N)$ circuit depth where $N$ is the number of qubits. The cap fidelity is based on the bond dimension $\chi$ which trades off memory and runtime with potential for squeezing more fidelity from the encoding.

The figure below compares state-of-the-art exact encoding with the MPS approach. The fidelities are placed below the figure:

MPS fidelities = [0.9999999999999998, 0.9999999999999996, 1.0000000000000002, 0.9999999999999987, 0.9999999999999976, 0.9999999999998372, 0.9993833081918707, 0.9856561882831156, 0.990348166799249, 0.9625191328840889, 0.9318239807292739]
MPS depths = [7, 13, 65, 73, 115, 121, 127, 133, 223, 229, 235]
Isometry depths = [3, 9, 23, 53, 115, 241, 495, 1005, 2027, 4073, 8167]

2. Performance expectations

MPS are mathematical representations for approximating 1D tensor networks efficiently. That being said, it represents entanglement within a 1D chain where longer entanglement range equates to deeper circuits. Data that is short-range entangled like images are perfect for such a compiler and are useful for state preparation blocks in QML use-cases. However, the focus is to provide the improvement over Isometry for arbitrary states.

MPS boasts $O(N)$ depth scaling, thus it significantly reduces the circuit depth and thus the 2 qubit gates.

Develop your compiler pass

Once the maintainers have given you the go-ahead, you can work on the next sections:

3. Create a fork of UCC to develop in: [link your fork here]
   Hint: We recommending syncing your fork with the main branch of UCC to stay up to date with changes.

4. Implement and Validate a Prototype of the Pass:
   A Jupyter notebook or a small script is sufficient for the prototype: [link prototype script/notebook here].
   Important: Make sure your compiler pass works as you expect on the circuits you defined in step 2a.

5. Implement the New Pass in the UCC Codebase:
   Documentation to guide you through this process is available in the user guide. For more detailed information and examples, refer to the Qiskit documentation.

Fork: https://github.com/ACE07-Sev/ucc
Link to notebook: https://github.com/ACE07-Sev/ucc/blob/main/ucc/aqc/testing%20mps%20sequential.ipynb

Benchmark performance

UCC benchmarks live in the separate repo called ucc-bench. We have a suite of quantum circuits that we regularly benchmark UCC and other popular quantum compilers on. Several of the key metrics we track are:

• Compiling alone:

  • 2-qubit gate count after circuit compilation (lower is better)
  • Total runtime of compilation (lower is better)

• Simulating compiled circuits:

  • Relative errors in simulated expectation values for a defined set of observables (lower is better)

Your new pass should improve one or more of these metrics on our existing benchmark suite.

Note: If you are introducing a technique whose effect on performance is not currently measurable by our benchmark suite (e.g. a new qubit mapping pass that performs very well on sparsely connected qubit layouts), let us know and we can work with you to add the metric into ucc-bench.

When you are ready to run benchmarks...

6. Open a pull request (PR) to merge your fork of UCC in main (mark it as a Draft unless you are ready for final review), ping a UCC maintainer, and we will trigger the benchmarking suite to run. Alternately, you can also run the benchmarks locally by comparing your UCC version to main, as explained in the ucc-bench README.

---

Useful documentation

Contributing Guide
Setting up your Developer Environment
Writing a Custom Transpiler Pass
-We use "transpiler pass" to refer to transformations that act only on the Directed Acyclic Graph (DAG) representation of the quantum circuit. Higher or lower-level optimizations (e.g. algorithm-level or pulse-level, respectively), we call "compiler passes."

[ACE07-Sev]

This can be used as a compiler as well as a transpiler.

compiler: Compiles statevector to circuit
transpiler/compressor: Extract statevector/MPS of circuit, and prepare that for a much shallower circuit

[jordandsullivan]

Thanks for your proposal @ACE07-Sev . So this would be the first approximate encoding pass in UCC. We haven't previously compiled differently based on logical features of a circuit (e.g. if it's an MPS or quantum chemistry problem, etc.), but this is a potentially interesting direction. This could be the start building out an approximate encoding module.

Next step would be to build a prototype which tests the circuit -->state vector -->MPS workflow for one of our benchmark circuits, track the number of gates, and simulate and evaluate the overlap of the MPS encoded circuit with the exact solution.

[ACE07-Sev]

So, choose a few different circuits, generate them for difference qubit sizes, get their statevector (no need to convert them to MPS. MPS is useful for two reasons, one is to perform the encoding given it's the core of the algorithm, and two is for calculating the inner product efficiently but it's not needed explicitly speaking), and then encode that statevector using sequential and compare the fidelity and depth. Did I get all that correctly?

[jordandsullivan]

Yep, that's correct!

[ACE07-Sev]

Copy that. I'll be done in a bit. Quick question, where do I put it for the PR?

[jordandsullivan]

So following the directions above in the Developing Your Pass section, if you've already forked UCC, you'll start with the prototype and then submit a PR to merge your fork when you've got a version integrated into UCC and have demonstrated improved benchmarks :)

[ACE07-Sev]

Copy.

[jordandsullivan]

@ACE07-Sev Let us know if your have any questions or need any support on this compiler pass :)

[ACE07-Sev]

Greetings there,

Hope you're doing well. No I don't need help, just not permitted to make a PR because I didn't know we had to keep PRs under 4, so have to wait until the other PRs are closed before they allow me to make a new one.

I finished the code same day as when I posted the discussion. I can discuss it though:

• I noticed for random clifford circuits it performs rather poorly (usually I have 0.95 fidelity) but this gets right back up to 0.95+ with optimization that I did for qmprs. So, Ran approach by itself will be great for random statevectors, but may not be super great for certain circuits (really grateful by the way, I wouldn't have noticed the random Clifford circuit result with MPS if it wasn't for this project).
• I noticed you also wrap alot of packages into ucc, so I was going to suggest integrating qmprs itself into ucc. I maintain that actively, it is currently state-of-the-art, and will make it less code on your side. Only issue is that qmprs is built with quick and quick is rather heavy since it integrates alot of circuit frameworks.

I'm going to make a PR for both scenarios (single PR, but two .py to showcase both approaches), and you can choose which one you prefer.

[jordandsullivan]

Hi @ACE07-Sev thanks for the update! We've decided to make an exception for the PRs you mentioned above since we already had this discussion going. You can go ahead and submit the PRs for UCC.

[ACE07-Sev]

Thank you so much. I'll be done in a few moments.

[jordandsullivan]

Cool @ACE07-Sev , can you let us know if you need any support on this? :)

[ACE07-Sev]

Sorry, was making the notebook nice. Making the PR now.

[jordandsullivan]

All good thanks! Will review the PR today.

[jordandsullivan]

Just tracking here, I went ahead and reviewed your PR

The prototype notebook looks good, so your next step will be 5. Implement the New Pass in the UCC Codebase (refer to comments on the PR for details)

If you wouldn't mind, please also edit the original Discussion post to link your fork of UCC and the demonstration notebook, just so we have everything in one place :)

[ACE07-Sev]

Copy that.