Add 2D Hidden Linear Function problem

[vtomole]

These problems can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). These would be interesting programs because they don't use oracles.

Refer to: https://arxiv.org/abs/1704.00690 https://arxiv.org/abs/1904.01502

[jitendrs]

can you please assign to me?

[jitendrs]

Thanks @vtomole

[fedimser]

Hi Victory, can you please assign it to me unless @jitendrs is planning to work on it? @vtomole

[fedimser]

Hi, I implemented circuit for Hidden Linear Function from the first paper (https://arxiv.org/pdf/1704.00690.pdf). I put it in Jupyter Notebook in my repository, please take a look: https://github.com/fedimser/quant_comp/blob/master/2D%20Hidden%20Linear%20Function.ipynb

I have some questions:

1. What should be the format? I noticed that most examples in Cirq are just Python files, but I personally find Jupyter Notebooks more convenient for examples.
2. Which parts of the paper should be in the example? I skipped all the proofs, and focused on implementing the circuit. Of course, I cited the paper where needed.
3. I didn't implement "2D Hidden Linear Function", just "Hidden Linear Function". Is this ok? The difference is that 2D HLF restriction of HLF on some sets of inputs. It's important for the paper because only in restricted case it's possible to show the advantage of quantum algorithm over classical. But the difference in implementation is just adding a graph algorithm (coloring the edges of grid graph in 4 colors), which has nothing to do with quantum computing.
4. I don't understand why in fig.1 authors needed to make A and b qubits. I think they can be just classical bits, and this doesn't make any difference. So, I didn't make them qubits to keep my circuit smaller. Hope this is fine.

If this notebook is good, I will copy it to examples in this repository.

@vtomole @viathor

[vtomole]

1. Notebooks are great! We need more notebooks in examples/.

2. Proofs will make the notebook too long. As long as the reader can follow how the circuit follows from the formulas, it's good.

3. I think implementing 2D Hidden Linear Function is important because I would want to link this notebook to people who ask questions like: https://quantumcomputing.stackexchange.com/questions/10009/how-can-we-compare-quantum-algorithms-against-classical-equivalents

4. I'd have to look at the paper again. I'll try to read your notebook before this week's sync.

[dstrain115]

If you want to do this as a jupyter notebook, I would recommend putting it in docs/notebooks as an example (don't add it to table of contents yet). I am working on putting together a nbsphinx converter to convert these to markdown automatically and then adding a section for "case studies", where we will go into an in-depth example.

In general, I would imagine that the goal of this should be two-fold. #1 priority is to show how to do this in cirq, and #2 priority is to explain the problem in more depth. I would focus on these objectives rather than try to reproduce results from the paper.

My comments for review.

Introduction: Would recommend putting an embbedded link to the paper instead of a reference so people can directly click on it. I don't think "cirquit" is an actual term and would just say "solve it using a cirq Circuit".

The problem: I would add more information here for background. If this is to help people understand the problem better, they should have more background before jumping straight into mathematical definition.

Preparation and brute force: Add many comments and doc strings to the code. Remember, the goal is to illustrate how to do the task. Also, at the end, you print out two numbers, but don't really explain what those two numbers are.

Solution with a quantum circuit: Change "# Given adjacency matrix A ..." in In[5] to a python docstring rather than single line comments. cirq.H(qubits[i]) for i in range(problem.n) can just be cirq.H(q) for q in qubits cirq.S.oncan just becirq.S` I would generally add more explanatory test to this section to explain the solution and what it is doing.

Why is this problem interesting: I would put this section at the beginning as a sub-section to introduction as a way of introducing the problem.

[fedimser]

Thanks, Doug! I will address your comments and create a PR adding this notebook to docs/notebooks. I'll try to do that tommorow.

[fedimser]

Created PR with a notebook, please review. @dstrain115

[dstrain115]

This has been completed and is now available on readthedocs and in the repo: https://cirq.readthedocs.io/en/latest/tutorials/hidden_linear_function.html