microsoft / microsoft/qdk

Shared abstraction for booleans and qubits

Open
#484 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement language
Dominant language
Rust
Stars
1k
Forks
212
Avg merge
3d 8h
Merged PRs (30d)
65

Description

From microsoft/qsharp-language#58:

> **Suggestion**
>
> When writing arithmetic code, there is a tendency to repeat the same method multiple times based on whether certain inputs are quantum or classical. For example, you would have one method for xoring a LittleEndian into another LittleEndian, and a separate method for xoring a BigInt into a LittleEndian. It would be convenient if there was instead a xor method that accepted a BigIntOrLittleEndian and handled both cases.
>
> This doesn't just apply at the level of designing methods. It also occurs when writing methods. For example, suppose you are creating a binary tree of qubits representing the AND of leaf input qubits as follows:
>
> ```
> let n = Length(input_qubits);
> using (work_qubits = Qubit[n-1]) {
> let qs = input_qubits + work_qubits;
> for (i in 0..n-2) {
> CCX(qs[2*i], qs[2*i+1], qs[n+i]);
> }
> ```
>
> One of the problems you will run into is that if `n` is not guaranteed to be a power of 2, then the qubit at position n+n/2 is talking about a mix of leaf qubits at the end of the input and intermediate node qubits representing leaf qubits at the start of the input. To fix this, you can pad out to a power of 2:
>
> ```
> let n = CeilPow2(Length(input_qubits));
> using (work_qubits = Qubit[2*n-Length(input_qubits)]) {
> let qs = input_qubits + work_qubits;
> for (i in 0..n-2) {
> CCX(qs[2*i], qs[2*i+1], qs[n+i]);
> }
> ```
>
> The problem now is that you are allocating unnecessary qubits to simplify your code. But if you were able to make an array of qubits-or-bits, and `CCX` understood that when one of its controls was a bit it should become a `CX` or no-op as appropriate, then you could do this:
>
> ```
> let n = CeilPow2(Length(input_qubits));
> let padding = RepeatArray(n - Length(input_qubits), False);
> using (work_qubits = Qubit[n-1) {
> let qs = input_qubits + padding + work_qubits;
> for (i in 0..n-2) {
> CCX(qs[2*i], qs[2*i+1], qs[n+i]);
> }
> ```
>
> And everything would just work. Although to be fair this is still not perfect; the unnecessary allocation is half as large but still there.
>
> _Considerations_
>
> This is a bit tricky to add to the language because at the moment the language is very picky about types. There's no way to _say_ "this array contains a mix of qubits and bits", or "the control of this method can be a qubit or a bit".

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

The issue points to microsoft/qsharp-language#58 and names no repository files or tests. Start by reading that proposal and tracing how Q# represents types and operations such as CCX, BigIntOrLittleEndian, and mixed qubit/bit arrays. Done would require a concrete language design and implementation plan.

Written by the indexing model from the issue text.

Assessment

Domain
compilers, quantum-computing
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
18/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.