Questions tagged [algorithm]
For questions about quantum algorithms, that is, sequences of quantum gates, operations, and measurements, whose purpose which achieve some goal. Standard examples are Shor's and Grover's algorithms.
1,030
questions
2
votes
2
answers
53
views
What is period finding useful for in Shor's algorithm?
Could someone help me to understand the concept behind period finding in Shor algorithm?. I'm a beginner in quantum computing.
I want to know why we use Shor's algorithm to find the period and what is ...
1
vote
0
answers
7
views
How does Functional Completeness look like in the quantum world?
Can Post's theorem help to elucidate the nature of quantum logic or other non-classical logics? Quantum logic uses a different set of logical connectives than classical logic, which makes questions of ...
- 111
0
votes
1
answer
17
views
Quantum algorithms and binomial distributions and probabilities
Qubits in a quantum computer are mostly spins of quantum particles.But since spin can take up to 2 values does this mean quantum algorithms are applied mathematics which make use of binomial ...
- 103
1
vote
1
answer
51
views
How to convert a basic matrix into a quantum circuit?
Classical gates are not invertible, but larger expressions made from those gates can be invertible. One example of an invertible function is the function $f(A,B,C) = X,Y,Z$:
$X = A \ B \ | \ \neg B \ ...
- 13
1
vote
0
answers
39
views
Which applications of quantum singular value transformation use block-encodings in apriori unknown bases?
Quantum singular value transformation (QSVT) algorithm allows performing polynomial transformations on matrices that are block-encoded in a unitary. Typically, block encoding is assumed to be 'the top-...
- 1,395
1
vote
1
answer
39
views
Controlled unitaries in quantum singular value transformation
tldr -- Building general polynomials with QSVT requires implementing controlled versions of vanilla QSVT circuits. Is this a trivial task? Does it change the complexity? How is it done in practice?
...
- 1,395
1
vote
1
answer
84
views
The difference between the Deutsch-Jozsa Algorithm and the Bernstein-Vazirani Algorithm
I am reading a book section about the difference between the Deutsch-Jozsa and the Bernstein-Vazirani Algorithm and here is the text:
As with DJ, the goal of BV is also to ascertain the nature of a
...
- 259
0
votes
0
answers
17
views
How does using a controlled rotation gate , with the slope of the linear function as a parameter, loads that function onto the amplitude?
I was going through the paper Quantum Risk Analysis in the section III they came up with a technique, in which they represented the analytical function into a polynomial and then used the slope of ...
1
vote
1
answer
25
views
How to add noise mode in Sampler (SamplerQNN) in qiskit for quantum neural network?
I would like to add a noise model to one of the tutorial examples of quantum machine learning in the Qiskit site (PyTorch QGAN implementation).
I used the following codes
...
- 11
4
votes
0
answers
88
views
How does edge-coloring help for quantum walks?
Reviewing Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman's famous 2002 welded-trees problem, a quantum Theseus can find his way out of a labyrinth having an exponential number of rooms (vertices),...
- 9,366
1
vote
2
answers
100
views
Can simulations of a quantum algorithm on a classical computer out-perform a classical algorithm?
Has it ever been shown that simulation of a quantum algorithm (e.g., using PyQuil or something?) on a classical computer has out-performed a purely classical algorithm? From what I can tell the ...
- 51
2
votes
1
answer
58
views
In Grover's algorithm for database search, how are non-queried fields handled?
I've read a lot about the Grover algorithm, and even got beyond the point of understanding the "magic" beyond the oracle function.
What is yet unclear to me is, given an oracle function ...
- 21
3
votes
0
answers
47
views
When is a quantum algorithm considered to have a significantly superior performance over another quantum algorithm?
Suppose we have two heuristic quantum algorithms $A$ and $B$ that attempt to solve a certain class of optimization problems. Let's suppose that the benchmarking metric is Time To Solution (TTS), which ...
- 2,194
3
votes
1
answer
237
views
When running an arbitrary quantum circuit, can all of the entanglement be done up front?
I'm trying to think practically about how a circuit might get implemented on a real world quantum computer and have a specific question about circuit set-up. Imagine my computer is such that I can ...
0
votes
1
answer
28
views
Different Decodings for Union Find
I read a paper about the implementation of a quasilinear UnionFind Decoder for quantum error correction and it says that the last step of it is building a sparse forest and peeling it. My question is ...
- 1
3
votes
0
answers
32
views
How could one use Grover's algorithm to find pairs of elements?
Imagine we have a set of distinct natural numbers which we divide into two unsorted lists $A$ and $B$. Then, there is a third list $E$ containing pairs of (pairwise) distinct natural numbers. We would ...
- 31
6
votes
1
answer
180
views
How would HSP with $S_N$ work when the automorphism subgroup is (almost) equal to the symmetric group?
The graph isomorphism problem can be reduced to a case of the hidden subgroup problem, with the group $S_N$ and the function $f \colon \pi \mapsto \pi(G)$ where $G$ is some graph, and $\pi \in S_N$.
...
- 227
1
vote
1
answer
134
views
Is QFT really faster FFT?
The standard DFT:
$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2 \pi kn/N} \tag{1}$$
takes approximately $N^2$ complex summations and multiplications (or $\mathcal{O}(N^2)$). The faster version of FT known as FFT ...
- 219
2
votes
1
answer
147
views
Why can't Bernstein-Vazirani algorithm be classicaly computed in one try?
Instead of using n inputs (000...01, 000...10, ..., 100...00) and multiplying each one with the hidden number x, why can't we just try one input: 111...11 ?
I can't think of an example of a binary ...
2
votes
0
answers
26
views
Quantum algorithms with few T gates?
Many existing quantum algorithms require millions or billions of T gates to reach a scale that is classically hard to simulate. However, existing Clifford + T circuits seem hard even with 100 or so T ...
- 133
0
votes
2
answers
73
views
circuit for quantum simulation?
What would be the circuit for operation exp(iθZ⊗Z⊗Z⊗X) by only using CNOTs and single-qubit gates. And How we can improve the circuit to implement the operation exp(iφZ⊗Z⊗X⊗Z ).exp(iθZ⊗Z⊗Z⊗X).Are ...
- 31
2
votes
0
answers
38
views
The quantum natural gradient descent problem
I was wondering if you could help me understand Quantum Natural Gradient Descent. I've been reading some papers related to it, such as "Quantum Natural Gradient" by James Stokes el al. and ...
2
votes
1
answer
38
views
Randomness and precision of Quantum Number Random Generators
I am reading about the problem of generating random quatum numbers, and I am interested in the state of the art in terms of the true randomness these generators achieve.
As far as I know, following ...
- 121
1
vote
2
answers
145
views
Can a quantum computer break a hash function?
I was watching this video by veritasium, https://www.youtube.com/watch?v=-UrdExQW0cs I'm curious on whether or not a quantum computer could break a hash function.
I'm not really sure how hash ...
0
votes
1
answer
58
views
Trying to replicate old code, migration guide unhelpful
I am trying to replicate and update some old code that had some aqua imports. Unfortunately the migration guide on github is unhelpful and the one it links is broken.
It has the following imports:
<...
- 13
2
votes
1
answer
45
views
Do I need an oracle for the powers of the unitary operator U for quantum phase estimation?
Quantum phase estimation is usually explained via repeated applications of controlled $U^{2^k}$ gates in order to realize the map
$$
|j\rangle|\psi\rangle \mapsto |j\rangle U^j|\psi\rangle
$$
If I ...
- 123
1
vote
0
answers
26
views
Pure Product State Problem Clarification about $\alpha$-closeness and $\beta$-farness
I am reading a paper on entanglement, specifically, determining if a state is close to being entangled or not.
The problem first introduces the $(\alpha, \beta, l)$-Pure product state problem. This ...
- 383
0
votes
0
answers
36
views
N-qubit VQE ansatz to generate all states?
I have found ansatzes that generate every state for certain specific values of n. However, I want to be able to write a function where I can pass in a value n (number of qubits) and be returned an ...
- 85
2
votes
0
answers
38
views
Converting from amplitude encoding to basis encoding
The question is inspired from Preparing a quantum state from a classical probability distribution which shows how basis encoding $\frac{1}{\sqrt n}\sum_{x=0}^{n-1}|x\rangle|p(x)\rangle$ may be ...
- 31
0
votes
0
answers
30
views
What is reservoir computing in simple terms, and how can it be used with quantum computing?
For those who are familiar with the notion of Reservoir Computing, can you explain the concept with simple terms and how it can be used with quantum computing ?
- 266
1
vote
0
answers
39
views
Quantum algorithm with $|y\rangle \mapsto (-1)^{xy}|y\rangle$ for all $y$ with at most $T$ many $1$s
Given an N-bit string $x$, which we can access by queries, give a quantum algorithm that maps $$|y\rangle \mapsto (-1)^{xy}|y\rangle$$ for all $y \in \{0,1\}^{N}$ that have at most T many $1$s and the ...
- 35
7
votes
1
answer
122
views
Is it possible to perform search with $O(\sqrt{N})$ copies of a "resource" state rather than an oracle?
Suppose that we wish to find $x$ s.t. $f(x) = 1$. Instead of having access to an oracle like $U_f: |i\rangle \mapsto (-1)^{f(i)}|i\rangle$ or $U_f: |i\rangle|z\rangle \mapsto |i\rangle|z\oplus f(i)\...
- 625
0
votes
0
answers
32
views
Problems in quantum computing that tolerate high error rate
It is proven that quantum computers outperform classical computers in several algorithms. Meaning with enough qubits quantum computer will find answer to large enough search faster than classical ...
- 1
10
votes
2
answers
701
views
What is the complexity of determining if a state is entangled?
I have been looking around for an answer to this question but can't really come up with anything. Given some oracle, $U$, that maps $| 0 \rangle$ to $| \psi \rangle$, is there some algorithm that ...
- 383
2
votes
1
answer
108
views
Detailed references on Quantum Principal Component Analysis
I am looking for review articles and other online resources on qPCA based on Lloyd's original proposal. I have found the original source to be slightly hand-wavy with the details so I am having ...
- 148
2
votes
1
answer
42
views
How to represent two gates addition on Qiskit composer. we can do tensor product and multiplication but how to do Addition
How to represent two gates addition on Qiskit composer we can do it in python code by using qiskit library but I would like to visually see how addition of two operators look like in composer.
I am ...
0
votes
0
answers
23
views
defining a unitary isometry
I am defining the coefficient unitary in full details but stuck. I tried many ways so that the cross terms gets cancelled and the diagonal terms has one.
- 1
2
votes
1
answer
124
views
How to apply QFT to the last two qubits of a Qiskit quantum circuit?
I'm pretty new in Qiskit and quantum circuits. I'm using Qiskit to implement a quantum circuit and I followed this tutorial to implement a QFT. The way this QFT was built, it applies QFT in the first $...
- 155
2
votes
2
answers
144
views
What exactly are "variational quantum algorithms"?
I constantly see papers on "variational quantum algorithms" but I don't really see any explanation of what they are that are clear to me.
I found out about the variational method in quantum ...
- 227
3
votes
1
answer
39
views
Is it possible to brute force the Salsa-20 algorithm with quantum computing in a reasonable amount of time?
I was recently attacked by the LockBit 3.0 ransomware. I researched it and found this article: LockBit 3.0 Ransomware Unlocked. It said that "files are encrypted using the Salsa-20 algorithm.&...
- 133
10
votes
3
answers
2k
views
Why can all quantum circuits be converted into circuits that use only real matrices?
I know that you need to add an additional ancilla qubit to "keep track" of whether or not you are in real space or imaginary space, but how exactly does this work?
What is the proof for this?...
- 309
4
votes
0
answers
71
views
Quantum Algorithm to Determine if two vectors are orthogonal
I have seen some sources use a quantum algorithm to estimate inner products between two states. The algorithm used from this answer is shown here:
But this algorithm has limitations; if the inner ...
- 383
2
votes
1
answer
40
views
Bounds on success probability of an algorithm under depolarizing noise
The problem I have is that, I have a quantum circuit performing a certain task (e.g. Shor's algorithm) and the circuit is subject to depolarizing noise, Pauli errors, after each gate. And I want to ...
- 53
1
vote
2
answers
55
views
Sorting two numbers using quantum computing
To better understand how quantum computing works, I am trying to sort two numbers using unitary matrix. Based on this definition, I understand a quantum Turing machine to have the automorphism (...
- 111
2
votes
2
answers
110
views
Quantum algorithm that "searches" for a particular state in a bigger state vector?
Does there exist an oracle that inputs a quantum state, say for example
$$
\frac{1}{2^N} \sum_{n=0}^{2^N - 1} \left | n \right > \left | f(n) \right >
$$
and allows us to find $n$ such that $f(n)...
- 359
0
votes
0
answers
44
views
HHL Algorithm for Classical Syndrome Decoding
Classical Syndrome decoding involves finding the e vector for the given syndrome s and Parity Check matrix H i.e., H.e' = s. This while implemented trying HHL Quantum Algorithm gives error after ...
- 11
4
votes
1
answer
174
views
Minimum number of 2-qubit gates required to implement a Toffoli gate
I'm trying to design a quantum circuit that has an output that is closest to a CCNOT gate with no more than four 2-qubit gates (but I can use additional single qubit gates).
A lot of resources/papers ...
- 41
0
votes
0
answers
52
views
Do I need a lab in order to test new ideas in designing quantum circuits
I would like to know how to test new ideas certainly on a circuit level. Do I require a lab? if so where can I find one I live in Houston. Does nt quantum eliminate the necessity of a lab and can I ...
- 19
1
vote
1
answer
98
views
A quantum circuit to find if 4 given sides can form a rectangle
I wrote this code that uses a swap test to find if 2 pairs of sides are equal.
First, amplitude encoding the 4 sides on 3 qubits then performing the swap test. I'm not sure where my logic went faulty, ...
- 15
0
votes
2
answers
229
views
How to compare 2 classical number using a quantum circuit
I'm given 2 numbers(could be positive/negative). I want to program a quantum circuit to compare them and return the greater one.
How can I do that?
Also, if the first step is encoding the numbers ...
- 15