Questions tagged [algorithm]

For questions on quantum algorithms. That is, algorithms which in theory can be executed by quantum computers, usually the computers providing 'universal' quantum computation.

Filter by
Sorted by
Tagged with
2
votes
1answer
45 views

Why can we forget about the ancilla bit in Grover's algorithm

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$ When using Grover's algorithm to invert a function $f\colon \{0,1\}^m \rightarrow \{0,1\}$, an ancilla bit is used in ...
-4
votes
1answer
70 views

What about this metaphor for quantum computing? [closed]

Suppose you have a large collection of N numbered copper coins. However, one of them is nickel but looks exactly the same as the rest. How do you find out which number the nickel coin has? Classical ...
2
votes
0answers
69 views

Could quantum computing improve chess engines?

Could and how quantum computing improve chess engines? Will it be able to think much faster and better than a classical chess computer? Will a quantum computing chess engine be drastically better ...
5
votes
1answer
73 views

The possibility of recovering the matrix $A+B$ from $e^{i(A+B)t}$ for Hermitian $A,B$

In the paper "Compiling basic linear algebra subroutines for quantum computers" here, the introduction seems to imply that the subroutines covered will touch on matrix addition and multiplication, ...
3
votes
1answer
77 views

How to prepare an initial state for variational quantum algorithms?

I would like to prepare an initial state for variational quantum algorithms. The initial state should include the following states: $|000\rangle, |010\rangle, |100\rangle$, and $|001\rangle$. How ...
3
votes
1answer
72 views

Showing that Matrix Inversion is BQP-complete - HHL Algorithm

I am trying to understand an argument that Matrix Inversion is BQP-complete for certain conditions on the matrix. This is explained here on page 39 (this paper is a primer to the HHL algorithm and ...
2
votes
1answer
35 views

Implementing the one-bit Deutsch Oracle algorithm using phase

The standard method of implementing the one-bit Deutsch Oracle algorithm is to use two qbits, one as input & one as output (which allows you to write the non-reversible constant functions in a ...
8
votes
4answers
357 views

Grover algorithm for a database search: where is the quantum advantage?

I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search. I ...
1
vote
0answers
59 views

What is the cost of implementing the Quantum Fourier transform in a classical computer?

What is the cost of implementing the Quantum Fourier transform (QFT) in a classical computer? We know we require at least $\log{n}$ depth quantum circuits to do a QFT in a quantum computer, with $n$ ...
2
votes
0answers
43 views

Quantum algorithms for Prolog or automated theorem proving?

Are there quantum algorithms for Prolog (SLD resolution - unification and depth-first-search) or for automated theorem proving in general (negation, resolution, and SAT)? Usually automated theorem ...
2
votes
1answer
39 views

Analysis of the second Hadamard in the Detusch-Josza Algorithm

Consider the Deutsch-Josza, algorithm, which first initializes the state $|0 \rangle^{\otimes n} | 1 \rangle$, creates a superposition using the the Hadamard gate and the $U_f$ to get into the state: $...
1
vote
1answer
45 views

How to understand run_algorithm() inputs in qiskit

I'd like to better understand the Max-Cut algorithm from the qiskit tutorials. Particularly, the run_algorithm function inputs. The inputs are two dictionaries, but I can't find any documentation or ...
2
votes
1answer
58 views

QAOA Maxcut for larger qubits

I am using QAOA to solve maxcut problem. It takes a very long time to simulate 10 qubits and I never get the results. Is there a way to simulate faster for larger qubit? Here is my code ...
2
votes
2answers
66 views

In Grover's Algorithm, does the exact solution need to be given to the oracle?

From my understanding, the oracle function in Grover's algorithm is used as a way to check for the desired outcome. I have looked at this example which implements the Exactly-1 3-SAT problem and the ...
1
vote
1answer
43 views

Variational Quantum Eigensolver (VQE) - Question about finding the imaginary part of measurement

I've been reading this article in order to understand how to implement a VQE on a quantum computer. Equation 38 involves the imaginary part of $ \langle\psi_0 |V_k^{j\dagger}(t)O_iU(t)|\psi_0\rangle ...
5
votes
3answers
224 views

Grover's algorithm in a nutshell

I am trying to understand Grover's algorithm. I read that this algorithm is able to find an entry in an unsorted list in just $\sqrt N$ steps, and needs only $\log N$ space. I understand entanglement ...
9
votes
1answer
277 views

Barren plateaus in quantum neural network training landscapes

Here the authors argue that the efforts of creating a scalable quantum neural network using a set of parameterized gates are deemed to fail for a large number of qubits. This is due to the fact that, ...
3
votes
1answer
59 views

How does the fact that the output of a quantum circuit cannot be efficiently simulated classically help for optimisation?

This question refers principally to the article where for a low-depth circuit QAOA, the output cannot be efficiently simulated classically. I am wondering how this kind of quantum supremacy matters ...
3
votes
0answers
29 views

QAOA and symmetry effects on the angles

In this paper, QAOA on Maxcut shows symmetries that allow them to restrict their search space intervals. But how do they find such intervals knowing that in the original QAOA angles $\gamma,\beta$ are ...
8
votes
1answer
1k views

What is the difference between QAOA and Quantum Annealing?

Edward Farhi's paper on the Quantum Approximate Optimization Algorithm introduces a way for gate model quantum computers to solve combinatorial optimization algorithms. However, D-Wave style quantum ...
3
votes
2answers
51 views

Is there a quantum algorithm allowing to efficiently determine the state with the highest probability of occurring?

Is there a quantum algorithm allowing to determine the state with the highest probability of occurring (i.e. highest square amplitude), more efficiently than repeatedly measuring and estimating a ...
1
vote
1answer
53 views

Newbie Project: Calculate a Mersenne Prime with Quantum Computing

I am new to the Quantum world and wondering the bounds of which the technology is at the current state of the art: specifically in computing prime numbers. I would like to, if possible, create a ...
1
vote
2answers
109 views

Software for Quantum Computing

From what I read classical computing evolved so quickly because of the funding-applications cycle. Even though the cost to make denser IC's was increasing rapidly, the applications were also getting ...
9
votes
1answer
48 views

Ground state energy estimation - VQE vs. Ising vs. Trotter–Suzuki

Disclaimer: I am a software engineer who is curious about quantum computing. Although I understand some basic concepts, theory and math behind it, I am by no means experienced in this domain. I am ...
5
votes
2answers
86 views

What is the point of building arithmetic circuits in a quantum computer?

My question simply is the following: is there any interests in building arithmetic circuits such as adders or multiplier on a quantum computer? I'm asking this because it seems that classical ...
3
votes
1answer
41 views

Would the Lattice Boltzmann Method be more suitable for QC CFD than Navier-Stokes?

First of all, let me come out and say that I know very little about Quantum Computing (QC), even though it's a subject which fascinates me. I'd say I'm generally aware of the basic principles (with a ...
3
votes
1answer
142 views

Quantum comparator with one fixed input

I currently need to implement efficiently a quantum comparator, with one of the values that is known at generation-time. In other words, I am searching for a quantum routine ...
10
votes
5answers
1k views

How would I implement the quantum oracle in Deutsch's algorithm?

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
2
votes
1answer
57 views

Expected value of a product of the Pauli matrices in different bases

I'm trying to reproduce the results of this article https://arxiv.org/abs/1801.03897, using Qiskit and Xanadu PennyLane. Particularly, this part with expected values of the Pauli operators: For ...
5
votes
3answers
330 views

Why is the application of an oracle function not a measurement?

Why is the application of an oracle function not a measurement, causing the collapse of the system? How can you know the state of the system (the input of the oracle function) without measurement?
4
votes
1answer
296 views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
9
votes
1answer
346 views

Grover's algorithm: what to input to Oracle?

I am confused about what to input to Oracle in Grover's algorithm. Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the ...
4
votes
0answers
27 views

Oracle for welded tree walk

There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical ...
3
votes
0answers
35 views

Are there any quantum algorithms to compute the norm of a vector, better than the classical version (O(d), where d is dimension)

I am researching how to speedup optimization problems using quantum algorithms. Many such algoritms use the Euclidean norm of a vector. Hence, I tried to find a quantum algorithm that speedups the ...
7
votes
0answers
89 views

What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
3
votes
0answers
126 views

What can be some bachelor thesis ideas in quantum random walks? [closed]

Note: Cross-posted on Theoretical Computer Science Stack Exchange. I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
2
votes
1answer
149 views

Grover diffusion operator different gates

I have two gates here for the Grover diffusion operator. The first gate is completely understandable for me, so I implemented it myself after submitting some papers that I read. This is the first ...
0
votes
1answer
101 views

If I have a state $a|0000\rangle+b|0011\rangle$, how do you change it to make $b>a$?

How to increase the amplitude of a specific quantum state? If my quantum circuit produces the state $a|0000\rangle+b|0011\rangle$, how to make $b>a$?
26
votes
3answers
2k views

Is there a layman's explanation for why Grover's algorithm works?

This blogpost by Scott Aaronson is a very useful and simple explanation of Shor's algorithm. I'm wondering if there is such an explanation for the second most famous quantum algorithm: Grover's ...
3
votes
2answers
72 views

Is the intuition of quantum parallelism always correct?

I recently read in Section 7.5.2 of Quantum Computing: A Gentle Introduction by Eleanor Rieffel and Wolfgang Polak a section in which they criticize the view of quantum parallelism in quantum ...
1
vote
1answer
47 views

Clarification of a portion of the paper Quantum Amplitude Amplification and Estimation

I am reading the paper "Quantum Amplitude Amplification and Estimation", available here (pages 4 to 7 in particular). I will try to summarize my confusion over a statement on page $7$. Suppose that $...
6
votes
1answer
201 views

Why is this implementation of the order finding algorithm not working?

I asked a question about this earlier, but I am still coming across problems in my algorithm implementation. I am trying to implement the order finding algorithm on Cirq finding the minimal positive $...
2
votes
1answer
29 views

Loading the finite precision representation of the norm of a vector into a computational register using CNOT gates

In the paper, Quantum linear systems algorithms: a primer, available here page 23, the authors discuss encoding a vector in $\mathbb{R^n}$ into qRAM. For $x \in \mathbb{R}^n$, let $|x \rangle := ||x|...
-2
votes
2answers
115 views

The most important quantum question , how to force a superposition qubit to collapses to an exact value? [closed]

Note: forcing a superposition qubit to collapses to 1, means cancel the other value 0 to get 1 appear Question details step by step: ...
0
votes
1answer
41 views

What is $\mathbb{Z}_2$ symmetry?

I encountered the notion of $\mathbb{Z}_2$ symmetry in an article. Can someone give a definition?
6
votes
1answer
128 views

What happens with first phase factor in QFT?

I'm using Mermin's Quantum Computer Science book to understand Shor's algorithm, but I can't figure out why one of the phase factors drops out of the probability for measuring a certain y. This is ...
1
vote
0answers
15 views

Ansatz Techniques to Multi-Body Physics Problems

I have been reading this paper: https://arxiv.org/abs/1906.01563v1. I am wondering: is it possible to use the idea behind quantum circuits to build classical Hamiltonians represented in the same way?...
1
vote
1answer
38 views

What does a zero state combined state vector for 2 qubits mean?

I was fiddling with the quantum circuit used for Deutsch's algorithm and I was led to a zero state as a result which is bizarre. I don't know how to explain this result. ***I'm using Nielsen and ...
12
votes
3answers
635 views

How is the Grover-Algorithm applied to a database?

Question I want to use the Grover-Algorithm to search an unsorted database for an element $x$. Now the question arises, how do I initialize index and value of the database with the qubits? Example ...
3
votes
0answers
92 views

Quantum Optimization via Quantum Label Classification in Quantum Circuits

I have been reading Farhi and Neven's paper on quantum neural networks on quantum circuits. I also found an example - albeit not ideal as pointed out by a couple of users - thank you - in here. ...