Create a generalized uniform superposition state gate

[prag16]

Creates a generalized uniform superposition state, $$\lvert \Psi \rangle = \frac{1}{\sqrt{M}} \sum_{j=0}^{M-1} \ket{j}$$ (where $1 < M \leq 2^n$), using $n$ qubits, according to the Shukla-Vedula algorithm [SV24]. Note that when $M$ is of the form $2^n$, creating uniform superposition states is trivial (just apply $n$ Hadamard gates on $\ket{0}^{\otimes n}$). However, in the general case, when $M$ is not of this form, creating uniform superposition states is non-trivial. The Shukla-Vedula algorithm [SV24] offers an efficient approach for the creation of a generalized uniform superposition state $ \lvert \Psi \rangle$ (as defined above) requiring only $O(\log_2 (M))$ qubits and $O(\log_2 (M))$ gates. This provides an exponential improvement (in the context of reduced resources and complexity) over other approaches in the literature.

Args: M (integer): A positive integer $M (> 1)$ representing the number of computational basis states with an amplitude of $\frac{1}{\sqrt{M}}$ in the uniform superposition state $$\lvert \Psi \rangle = \frac{1}{\sqrt{M}} \sum_{j=0}^{M-1} \ket{j}.$$ Note that the remaining $(2^n - M)$ computational basis states have zero amplitudes. Here $M$ need not be an integer power of $2$.

    n (integer): 
        A positive integer representing the number of qubits used.

Returns:
    A quantum circuit that creates the uniform superposition state: $$\frac{1}{\sqrt{M}} \sum_{j=0}^{M-1} \ket{j}$$. 

References: [SV24] A. Shukla and P. Vedula, “An efficient quantum algorithm for the preparation of uniform quantum superposition states,” Quantum Information Processing, 23(38), pp. 1-32 (2024).

[google-cla[bot]]

Thanks for your pull request! It looks like this may be your first contribution to a Google open source project. Before we can look at your pull request, you'll need to sign a Contributor License Agreement (CLA).

View this failed invocation of the CLA check for more information.

For the most up to date status, view the checks section at the bottom of the pull request.

[prag16]

@vtomole @dstrain115 - The code appears to be working fine on my end. Could you please review it and provide your feedback?

[tanujkhattar]

What's the use case for this? Why are we adding this to Cirq?

However, in the general case, when is not of this form, creating uniform superposition states is non-trivial.

Uniform superposition states can be prepared using a single round of amplitude amplification using a single ancilla qubit. See https://github.com/quantumlib/Qualtran/blob/b9c5b5bd33d17f35fe027ff5362dd0b2f6887048/qualtran/bloqs/state_preparation/prepare_uniform_superposition.py#L29 for more details.

Can you highlight what's the difference of your approach against previously known results like Fig 12 of https://arxiv.org/pdf/1805.03662.pdf which is implemented in the Qualtran link I've shared above? Also, I think Qualtran might be a better repository for algorithmic primitives like this.

@dstrain115 Is this needed in Cirq for a specific use case I'm not aware of?

[prag16]

@tanujkhattar Thanks for your comments. Please note the following points about the approach suggested in Fig 12 of https://arxiv.org/pdf/1805.03662.pdf vs the approach used in the code in this PR: (1) The approach in the arxiv reference requires 2⌈log L⌉ + O(1) qubits (in the interesting case when L is odd), which is double the number of qubits needed by the submitted code in this PR (2) The T count given in the arxiv reference is 2k + 10 log L + O(log( 1/ϵ )) with a dependence on O(log( 1/ϵ )), The submitted code in this PR needs only O(log L) gates without any dependence on O(log( 1/ϵ )) term. (3) Lastly, but most importantly the submitted code is deterministic and 100% succeeds, whereas the code in the arxiv reference is probabilistic (it uses amplitude amplification). Theoretical computation shows that the probability of success can be significantly less (less than 12%) in many instances when one uses the probabilistic algorithm given in the arxiv reference.

Considering the above points, it seems the submitted code provides a simpler (just a few lines of code), cleaner, and deterministic approach for the preparation of uniform superposition states as compared to the probabilistic approach given in the arxiv reference.

Next coming to - What's the use case for this? Why are we adding this to Cirq? I guess creating uniform superposition states is an important algorithm - it is the first step in many important quantum algorithms - including the case when the number of uniform superposition states N is not of the form of 2^n, which will be useful for a variety of applications. I am open to your comments and suggestions.

[tanujkhattar]

Can you share a quirk link of the circuits produced by your algorithm and compare it with the circuits I've linked in the reference for a better understanding and comparison? See this link for what the circuit looks like for the linked reference

(1) The approach in the arxiv reference requires 2⌈log L⌉ + O(1) qubits (in the interesting case when L is odd), which is double the number of qubits needed by the submitted code in this PR

That's correct. The additional logL qubits are used in the LessThanGate oracle to minimize the T-count. \

(2) The T count given in the arxiv reference is 2k + 10 log L + O(log( 1/ϵ )) with a dependence on O(log( 1/ϵ )), The submitted code in this PR needs only O(log L) gates without any dependence on O(log( 1/ϵ )) term.

The dependence on O(log( 1/ϵ )) comes from how closely you approximate a single Ry(theta) rotation gate and is relevant in the fault tolerant regime. Your implementation also has this dependence since you use multiple small angle rotation of the form cirq.ry(theta) and controlled versions of it thereof.

(3) Lastly, but most importantly the submitted code is deterministic and 100% succeeds, whereas the code in the arxiv reference is probabilistic (it uses amplitude amplification). Theoretical computation shows that the probability of success can be significantly less (less than 12%) in many instances when one uses the probabilistic algorithm given in the arxiv reference.

The code in the linked reference is also deterministic. When you know the initial overlap, you can perform amplitude amplification to deterministically end on the good state. See the quirk link above to understand the circuit in the linked reference better.

[prag16]

@tanujkhattar Thanks for sharing the link. As you suggested, I am sharing the links to quirk circuits for the cases N=100, N=130, and N=127 based on the approach used in the submitted PR.
I think the above circuit for N=100 is much simpler compared to the circuit in the link that you provided for the same case. In other cases also, the provided circuits are very simple and efficient. The above circuits use fewer number qubits (which is consistent with what we discussed earlier about the arxiv reference requiring 2⌈log L⌉ + O(1) qubits which is double the number of qubits needed by the submitted code in this PR). The number of gates and the circuit depth in the submitted PR are considerably lower than the arxiv reference that you shared (which is consitent with the T count given in the arxiv reference 2k + 10 log L + O(log( 1/ϵ ))). The use of multi-controlled rotation gates and comparator circuits increases the circuit gate complexity for the approach given in the arxiv reference, whereas only at most single-controlled gates are needed in the approach that I shared.

Finally, typically algorithms involving amplitude amplification are probabilistic, unless one can show that the probability of obtaining the bad states is 0 after the amplitude amplification. This proof or the expression for the probability of success was not provided in the reference that you shared. However, The authors of the reference you shared have discussed the probabilistic nature of a later version of their algorithm (for preparation of uniform superposition states) in a later paper and provided an expression for the probability of success. Please refer to Eq. 205 and Eq. 206 and Figure 10 in Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

Even if we keep aside the discussion on the probabilistic nature of algorithm of the arxiv reference, considering the discussion above and the quirk circuits provided, it is clear that the submitted code in the PR provides a cleaner approach with fewer resources for the preparation of the uniform superposition states.

Overall, I think there is merit in the potential inclusion of the submitted code in Cirq framework.

[NoureldinYosri]

I have added the triage/discuss label so that we discuss this PR in the next cirq-sync meeting

@prag16 the next cirq-sync will be on May 8th. you can either join the cirq-dev group to get an automatic invitation or I can send you an invitation to the meeting (in that case which email should I use).

[prag16]

@NoureldinYosri Thank you for the invitation. I have joined the cirq-dev group and am looking forward to attending the next cirq-sync on May 8th.

[prag16]

@NoureldinYosri and @anurudhp: Thank you very much for all your helpful suggestions. I have made the suggested changes.

I am confident that the tests will pass now. Could you please run the tests to check if they are passing now?

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 99.02913% with 1 lines in your changes are missing coverage. Please review.

Project coverage is 97.81%. Comparing base (df07e94) to head (ac491bc).

:exclamation: Current head ac491bc differs from pull request most recent head 389260e

Please upload reports for the commit 389260e to get more accurate results.

Files	Patch %	Lines
cirq-core/cirq/ops/uniform_superposition_gate.py	98.43%	1 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## main #6506 +/- ## ======================================== Coverage 97.81% 97.81% ======================================== Files 1061 1063 +2 Lines 91658 91761 +103 ======================================== + Hits 89657 89759 +102 - Misses 2001 2002 +1 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[prag16]

@NoureldinYosri - I turned off the json-related tests temporarily to ensure that all the other tests are passing first (and we are pretty close to that). Next, after including the json-related functionality, I'll turn these tests back on and request your review.

[prag16]

@NoureldinYosri - I implemented the json-related functionality and turned on all the tests. All the checks are passing at my end. Can you please run the ci tests at your end to confirm?

[prag16]

@NoureldinYosri - Thanks for reviewing the changes. Now, I've corrected the formatting and added more tests to fix CI coverage check errors. Hopefully, the CI tests should pass now.

[prag16]

@NoureldinYosri - I have taken care of the last remaining coverage error and also fixed the format error. The CI checks are passing locally for me, Hopefully, the checks will pass at your end as well.

[prag16]

@NoureldinYosri - It is good that all the tests passed (except for the format check). I have fixed this issue now. Could you please run the CI tests on your end?

[prag16]

@NoureldinYosri - Thank you very much for reviewing the code and for your helpful suggestions! I really appreciate it!