Questions tagged [quantum-algorithms]

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
93 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-...
Nikita Nemkov's user avatar
1 vote
1 answer
126 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? ...
Nikita Nemkov's user avatar
1 vote
1 answer
272 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 ...
Hamideh's user avatar
  • 269
0 votes
0 answers
44 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 ...
user avatar
2 votes
1 answer
353 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 ...
Neda's user avatar
  • 21
4 votes
0 answers
153 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),...
Mark Spinelli's user avatar
1 vote
2 answers
122 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 ...
IsalanOnkar's user avatar
2 votes
1 answer
76 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 ...
Animo's user avatar
  • 21
4 votes
0 answers
62 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 ...
MonteNero's user avatar
  • 2,481
3 votes
1 answer
248 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 ...
Drplatypusrex's user avatar
0 votes
1 answer
58 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 ...
feder34's user avatar
4 votes
0 answers
45 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 ...
VVAV's user avatar
  • 41
6 votes
1 answer
194 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$. ...
Andrew Baker's user avatar
1 vote
1 answer
350 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 ...
Curious's user avatar
  • 259
2 votes
1 answer
156 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 ...
Confused engineer's user avatar
2 votes
0 answers
49 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 ...
shixian105's user avatar
0 votes
2 answers
133 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 ...
Jack's user avatar
  • 31
2 votes
0 answers
68 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 ...
Linh Nguyễn Vũ's user avatar
2 votes
1 answer
54 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 ...
Martin Hurtado's user avatar
2 votes
2 answers
1k 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 ...
Carson Ouckama's user avatar
0 votes
1 answer
160 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: <...
Mark McGuire's user avatar
2 votes
1 answer
73 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 ...
user3095304's user avatar
1 vote
0 answers
27 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 ...
Loic Stoic's user avatar
2 votes
0 answers
98 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 ...
Philips's user avatar
  • 31
0 votes
0 answers
50 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 ?
Duen's user avatar
  • 426
1 vote
0 answers
53 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 ...
kerf's user avatar
  • 35
7 votes
1 answer
131 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)\...
shashvat's user avatar
  • 805
0 votes
0 answers
43 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 ...
Physicst's user avatar
11 votes
2 answers
760 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 ...
Loic Stoic's user avatar
2 votes
1 answer
145 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 ...
Song of Physics's user avatar
2 votes
1 answer
133 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 ...
Nithin Reddy Govindugari's user avatar
5 votes
1 answer
1k 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 $...
Herr Schrödinger's user avatar
2 votes
2 answers
719 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 ...
Andrew Baker's user avatar
3 votes
1 answer
126 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.&...
Anston Sorensen's user avatar
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?...
Rydberg's user avatar
  • 309
4 votes
0 answers
119 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 ...
Loic Stoic's user avatar
2 votes
1 answer
71 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 ...
AndyLiuin's user avatar
  • 165
1 vote
2 answers
66 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 (...
Anon21's user avatar
  • 111
2 votes
2 answers
136 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)...
wavosa's user avatar
  • 399
4 votes
1 answer
540 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 ...
Sophie Block's user avatar
0 votes
0 answers
60 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 ...
Akram haidar's user avatar
1 vote
1 answer
116 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, ...
quark epsi's user avatar
0 votes
2 answers
680 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 ...
quark epsi's user avatar
0 votes
1 answer
64 views

Quantum problems that input arithmetic circuits

In computer science, problems can input arithmetic circuits. For example, let's just consider an example search problem: You are given an input $x \in \mathcal{I}$. $x$ is a tuple $(n, C)$, where $C$ ...
wavosa's user avatar
  • 399
1 vote
0 answers
60 views

Find the desire state with a set of gates?

I encoded a state |000> applied by a U3 gate, resulting in state: a|000>+b|100>. I need to create a circuit to achieve the desired state (a'|**0>+b'|**1>) with * as any 0 or 1 state. ...
Việt Nguyễn's user avatar
1 vote
1 answer
65 views

In the quantum mean computation circuit, how to apply the controlled rotation to the extra qubit?

I'm trying to implement quantum mean computation via amplitude estimation, as suggested in Example 8.3.5 in Kaye, LaFlamme, Mosca. I wonder about the actual circuit to accomplish this. This previous ...
rhundt's user avatar
  • 998
1 vote
1 answer
307 views

Deustch-Jozsa algorithm for a specific problem, doesn't make sense?

I am trying to implement Deustch-Jozsa Algorithm where function f(x) = 0 for even and f(x) = 1 for odd, for a four-bit number. After writing the numbers out I found a pattern as described below ...
JaZZyCooL's user avatar
4 votes
2 answers
628 views

Is there any quantum annealer simulator offered by DWave?

I am searching for quantum annealer simulator offered by DWave. I found classical solvers in dimod packages that implement simulated annealing, but I couldn’t find solver that simulates the real ...
SEB4N's user avatar
  • 41
5 votes
2 answers
333 views

Did Feyman cite Yuri Manin in his paper "Simulating Physics with Computers"?

In Feyman’s paper "Simulating Physics with Computers", did he cite Yuri Manin as the idea of a quantum automaton that used superposition and entanglement was mentioned in his book a year ...
WULFRIC BLACK's user avatar
1 vote
1 answer
94 views

Error Correction over time

I am in year 12 and am a Science Extension student. My research question was "To what extent does an error-correcting algorithm reduce the inaccuracy of a quantum computation over time?". To ...
Liam Mitchell's user avatar

1 2 3
4
5
24