Quantum Computing Stack Exchange
Quantum Computing Stack Exchange

Questions tagged [arithmetic]

23 questions
8
votes
4 answers

Computing $e^x$ on a quantum computer

Does anyone know how to make a quantum circuit to compute exponentials where the exponent can be a fraction? To be more precise, I'm looking for a fixed point quantum arithmetic circuit that does the following: $$|\vec{x}\rangle|\vec{0}\rangle…
sheesymcdeezy
  • 2,021
  • 8
  • 27
5
votes
1 answer

Why can't "oblivious carry runways" be fully removed from Gidney's implementation of Shor's algorithm?

Hoping that @CraigGidney can hop in here. I'm trying to understand oblivious carry runways and how it interplays with the rest of the windowed arithmetic implementation of Shor's algorithm as presented in "How to factor 2048 bit RSA integers in 8…
quantum_squirrel
  • 85
  • 4
4
votes
1 answer

Subtraction circuit in Vedral, Barenco, Ekert

I'm reading the paper Quantum Networks for Elementary Arithmetic Operations (arXiv) by Vedral, Barenco, and Ekert. In section IIIA, they define a quantum adder circuit that sends $$ |a,b\rangle\rightarrow |a,a+b\rangle $$ where $a$, $b$ are $n$-bit…
Jahan Claes
  • 1,092
  • 6
  • 13
4
votes
0 answers

What is the Toffoli-depth of a Multiplier

I am looking for the T-depth (or Toffoli-depth) of the smallest T-depth known quantum multiplier of 2 registers (specifically, I am into $x*x=x^2$), I will be happy for a reference and/or formula. I guess it will be one that is implemented with…
Ron Cohen
  • 1,512
  • 6
  • 24
4
votes
1 answer

On unitary matrix form suggested in the Elementary gates paper

In the "Elementary gates for quantum computation" paper Barenco et al. start their proofs by defining a generic form of $2\times 2$ unitary matrices as follows: Can you help me with the basic arithmetic behind this statement? For unitary matrix…
Grwlf
  • 143
  • 5
4
votes
3 answers

Is it possible to implement an in-place multiplication quantum circuit?

How can a reversible multiplication quantum circuit be implemented? By "reversible" I mean one that performs a *= b on the inputs a and b of the multiplication. In this case, it is reversible because the inverse operation a /= b exists. I believe…
yasuhito
  • 91
  • 4
3
votes
1 answer

How to verify a matrix-vector product with Grover search?

I am looking at the Ambainis et al. method of verifying whether $AB = C$ in $O(n^{7/4})$ queries, as described in Buhrman and Špalek. They have the following sentence: verify the matrix-vector product $Ay=z$ by a Grover search. What, exactly, does…
416E64726577
  • 135
  • 7
2
votes
1 answer

How do you set up Microsoft's Classic QDK?

Around the beginning of 2024, Microsoft replaced the "Classic" Q# quantum development kit with a new "Modern" QDK. Code written for the classic version can no longer can be run with the modern version. I’d like to be able to run the code from this…
Jahan Claes
  • 1,092
  • 6
  • 13
2
votes
1 answer

Implementation of modular prime number p multiplication

I am trying to implement small codes for quantum kernel estimation with Qiskit. In this challenge, I face the difficulty of implementing modular multiplication under a given prime number $p$. I have found some articles and a function in Qiskit to…
ksk S
  • 31
  • 2
2
votes
1 answer

Efficient creation of a modular multiplicative inverse gate using Fermat's Little Theorem

I'm wondering if anyone has ever stumbled upon an efficient way to create a gate that can calculate the multiplicative modular inverse in $\mathbb{Z}_p$, it may even be that somebody has stumbled upon it by accident, without being aware of Fermat's…
Ramezzez
  • 166
  • 6
2
votes
2 answers

Better constant for linear depth incrementers

Currently working on some quantum arithmetic and was wondering if we have a better constant factor for a linear depth incrementer. As an example (and the best I could currently find), Craig Gidney proposes an n-bit incrementer than scales with '32n'…
Ramezzez
  • 166
  • 6
2
votes
1 answer

Comparing qubit values in pairs of qubits

For $2N$ qubits $\{i_1,j_1\ldots i_N,j_N\}$ I would like to have a circuit changing the value of an ancillary register from $0$ to $1$ if $i_1=j_1$ AND $i_2=j_2$ AND ... AND $i_N=j_N$. One way to construct such a circuit is to use a separate…
mavzolej
  • 2,271
  • 9
  • 18
2
votes
1 answer

Oracle for amplitude addition

Assume one is given two oracle circuits providing access to matrices $A_{ij}$ and $B_{ij}$ as follows (see eq. (6.2) here): \begin{equation} O_A |0\rangle|i\rangle|j\rangle=\left(A_{ij}|0\rangle+\sqrt{1-|A_{ij}|^2}|1\rangle\right)|i\rangle|j\rangle…
mavzolej
  • 2,271
  • 9
  • 18
2
votes
1 answer

How can one sort two registers without leaving an entangled ancilla behind used for comparison?

If we have an state $\alpha|abc\rangle + \beta|bad\rangle$, and we know that $a
Pablo
  • 603
  • 3
  • 11
2
votes
1 answer

Formulate Controlled-Not as mapping (including modulo-2 addition)

We often see that the controlled-not gate is written as $CNOT |x y \rangle = |x\rangle |x \oplus y\rangle$. Now, would it be possible to further expand this to get a general equation? $$(\alpha_0 |0\rangle + \beta_0 |1\rangle) \otimes…
Fabian
  • 35
  • 4
1
2