Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [quantum-algorithms]

For questions on algorithms that could in theory be executed by quantum computers, usually the computers providing 'universal' quantum computation.

5
votes
0answers
22 views

Does the GLOA have any advantage over the Solovay-Kitaev algorithm?

The Solvay Kitaev algorithm was discovered long before the Group Leaders Optimization algorithm and it has some nice theoretical properties. As far as I understand, both have exactly the same goals: ...
2
votes
0answers
20 views

Why does Fourier sampling allow to efficiently recover hidden subgroups?

The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and ...
4
votes
2answers
68 views

Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?

I have been studying on Quantum Fourier Transform (QFT) by myself, and I am little bit confused about how could QFT be used. For example, if the QFT of three quantum bits is $a_1|000\rangle + ...
4
votes
3answers
134 views

Quantum Computing Project

I am currently working on a quantum computing subject for my coding school, and I had some questions for you. My objective would be to introduce students to Quantum Computing with an algorithmic ...
5
votes
1answer
44 views

Efficiently performing controlled rotations in HHL

This question builds off of this question. In the HHL algorithm, how do you efficiently do the $\tilde{\lambda}_k$-controlled rotations on the ancilla qubit? It seems to me that since you don't know ...
6
votes
3answers
64 views

$R_z$ gate representations

Why is the $R_z$ gate sometimes written as: $$ R_{z}\left(\theta\right)=\begin{pmatrix}1 & 0\\ 0 & e^{i\theta} \end{pmatrix}, $$ while other times it is written as: $$ R_{z}\left(\theta\...
2
votes
0answers
45 views

Simulating Read only QRAM (constructing an oracle)

In many algorithms an array that stores a classical data or quantum data is crucial. The QRAM (quantum random access memory) that stores classical data in the circuit has been done. My question ...
6
votes
0answers
47 views

How significant are the variants of Grover's Algorithm?

I found a paper by Grover titled "How significant are the known collision and element distinctness quantum algorithms?", in which he expressed criticism to several famous algorithms, including ...
5
votes
2answers
107 views

Is there a general method to implement a 'greater than' quantum circuit?

I am interesting in finding a circuit to implement the operation $f(x) > y$ for an arbitrary value of $y$. Below is the circuit I would like to build: I use the first three qubits to encode $|x⟩$, ...
7
votes
3answers
52 views

General construction of $W_n$-state

Two of the most well known entangled states are the GHZ-state $|\psi\rangle = 1/\sqrt{2}\left( |0\rangle^{\otimes n} + |1\rangle^{\otimes n}\right)$ and the $W_n$-state, with $W_3 = 1/\sqrt{3}\left(|...
4
votes
1answer
57 views

Applying CNOT With Local Operations and Two EPR Pairs

Suppose Alice and Bob hold one qubit each of an arbitrary two-qubit state $|\psi \rangle$ that is possibly entangled. They can apply local operations and are allowed classical communication. Their ...
5
votes
1answer
44 views

Quantum Algorithm for MIMO ML detection

I am reding the paper EXIT-Chart Aided Near-Capacity Quantum Turbo Code Design by Babar et al. and in the introduction, it is stated that due to the exponentially increasing complexity of the MIMO ML ...
4
votes
3answers
457 views

What's an use case of the inner product between two q-bits in a quantum algorithm?

$\newcommand{\q}[2]{\langle #1 | #2 \rangle}$ I know from linear algebra that the inner product of two vectors is 0 if the vectors are orthogonal. I also know the inner product is positive if the ...
4
votes
1answer
122 views

Qutrit Teleportation

I'm working through Scott Aaronson's Quantum Information Science problemsets, and I'm having trouble with a specific problem. Specifically the following problem: Here's what I've done: after applying ...
3
votes
1answer
67 views

How to create a condition on only one classical bit when we have a total of 2 classic bits in the system

I am trying to make a quantum circuit with one qubit and 2 classical bits for each measurment in the system below: I want to make condition on the first bit: if the first collapse to zero so x ...
1
vote
1answer
104 views

How to add two integers in Q#?

I have programmed in C++, but I am interested in writing quantum programs. I have some experience with Microsoft's Q#, and I know about the canonical Shor's and Grover's algorithms. Can anyone tell ...
6
votes
1answer
144 views

Decomposition of arbitrary 2 qubit operator

As you know, universal quantum computing is the ability to construct a circuit from a finite set of operations that can approximate to arbitrary accuracy any unitary operation. There also exist some ...
6
votes
4answers
151 views

Quantum Computing Journals

Can anyone give me a list of different research journals that has quantum computing articles that I can use.
11
votes
2answers
155 views

Are there any examples of anyone applying quantum algorithms to problems in computational biology?

As the title suggests, I'm searching for published examples of quantum algorithms being applied to problems in computational biology. Clearly the odds are high that practical examples don't exist (yet)...
8
votes
1answer
58 views

What is the Helstrom measurement?

I have been reading the paper Belief propagation decoding of quantum channels by passing quantum messages by Joseph Renes for decoding Classical-Quantum channels and I have crossed with the concept of ...
5
votes
1answer
43 views

Classical XOR gate in Quantum Circuit

Can we use classical XOR gate in a quantum circuit? Or are there any alternatives for XOR gate?
4
votes
1answer
136 views

Do we really know how a universal quantum computer can be used to revolutionize the design of new drugs or materials?

One of the most promising applications of a quantum computing is the design of new drugs and materials: Quantum computers promise to run calculations far beyond the reach of any conventional ...
3
votes
2answers
92 views

What do “hyperparallel algorithm” and “hyperentangled state” mean?

What do the terms "hyperparallel algorithm" and "hyperentangled states" mean? I found it mentioned here[1]. In the abstract they say: "Hyperentangled states, entangled states with more than one degree ...
4
votes
1answer
49 views

Quantum XOR Cipher Construction

After getting help here with XNOR, RCA & XOR linked lists, I am now curious about quantum XOR ciphers (Google returns "no results"). In cryptography, the simple XOR cipher is a type of ...
5
votes
3answers
191 views

How to speed up the matrix multiplication steps in multi-linear regression?

Context and Motivation: As discussed here, in multilinear regression, we can express the linear system as $AX = b$. This leads to $A^TA \hat{X} = A^T b$. From here, the estimated value of $X$ is ...
4
votes
3answers
149 views

Example of Hamiltonian Simulation solving interesting problem?

Hamiltionian Simulation (= simulation of quantum mechanical systems) is claimed to be one of the most promising applications of a quantum computer in the future. One of the earliest – and most ...
6
votes
1answer
128 views

Is there an intuition built on ansatz in VQE algorithm or is it more a trial and error approach?

Variational Quantum Eigensolver is a popular algorithm in Quantum Computing. But the ansatz part is very tricky. I do not really understand if they are built on some intuition, according to hardware ...
10
votes
2answers
2k views

Classical Memory enough to store states up to 40 qubits quantum system?

As a part of a discussion with my 'classical' friend, he insisted that making a a state machine for calculating the outcome of quantum computer is possible; so, simply calculate the outcomes of (known)...
9
votes
1answer
146 views

How would a quantum computer be used to solve Partial Differential Equations?

Say you have a PDE you want to solve. What kind of quantum algorithms would you use to solve it? How do we input our problem on a quantum computer? What will be the output and in what form? I know ...
4
votes
1answer
63 views

Is there a Hamiltonian simulation technique implemented somewhere?

I was wondering if there was some code available for Hamiltonian simulation for sparse matrix. And also if they exist, they correspond to a divide and conquer approach or a Quantum walk approach?
7
votes
2answers
59 views

What exacty is “matrix sparsity” $s$?

In many sources (like on Page 30 here), I found that the complexity of the original Harrow Hassidim Lloyd is stated as $\mathcal{O}(\log (N) s^2 \kappa^2/\epsilon)$ where $s$ is said to be the "matrix ...
6
votes
1answer
66 views

Does the need of many quantum algorithms to be repeated several times impair the efficiency gains?

As I understand so far, in some algorithms such as Simon's algorithm, swap-test algorithm or quantum k-means algorithm, we repetitively perform a measurement yielding a classical result. Consequently, ...
8
votes
2answers
184 views

Quantum Algorithms for Convolution

I was looking into applications of Quantum Computing for machine learning and encountered the following pre-print from 2003. Quantum Convolution and Correlation Algorithms are Physically Impossible. ...
7
votes
2answers
262 views

Inner product of a quantum states

I found an algorithm that can compute the distance of two quantum states. It is based on a subroutine known as swap test (a fidelity estimator or inner product of two state, btw I don't understand ...
9
votes
1answer
201 views

Quantum Algorithm for God's Number

God's number is the worst case of God's algorithm which is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles ...
7
votes
3answers
214 views

Simplest algorithm for intuitively demonstrating quantum speed-up?

What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively? Ideally this would be ...
6
votes
2answers
169 views

How do you implement the Toffoli gate using only single-qubit and CNOT gates?

I've been reading through "Quantum Computing: A Gentle Introduction", and I've been struggling with this particular problem. How would you create the circuit diagram, and what kind of reasoning would ...
10
votes
2answers
133 views

Can a quantum computer easily determine the mixing time of the Rubik's cube group?

Officials in Rubik's cube tournaments have used two different ways of scrambling a cube. Presently, they break a cube apart and reassemble the cubies in a random order $\pi\in G$ of the Rubik's cube ...
8
votes
2answers
101 views

Resources for Quantum Communication Complexity

I recently came to know about this interesting topic of "communication complexity". In simple words, Wikipedia defines it as: In theoretical computer science, communication complexity studies the ...
10
votes
1answer
83 views

Advantage of simulating sparse Hamiltonians

In @DaftWullie's answer to this question he showed how to represent in terms of quantum gates the matrix used as example in this article. However, I believe it to be unlikely to have such well ...
5
votes
0answers
29 views

Are non-secret-based quantum money mini-schemes susceptable to Jogenfors' “reuse attack?”

Aaronson and Christiano call public-key or private-key quantum mini-schemes $\mathcal M$ secret-based if a mint works by first uniformly generating a secret random classical strings $r$, and then ...
5
votes
1answer
57 views

Can a qubit register hold any subset of values, or only specific subsets?

Say I have a quantum register containing 1 qubit. A qubit can hold either 0, 1 or both 0 and 1. In Dirac, one would write 0: $|0\rangle=\begin{bmatrix}1\\0\end{bmatrix}$ 1: $|1\rangle=\begin{bmatrix}...
7
votes
2answers
87 views

Does “quantum registers with $n$ qubits are able to hold $2^n$ values and therefore scale exponentially” actually hold that straightforwardly?

A lot of people claim that quantum provides exponential speedup whereas classical computers scale linearly. I have seen examples (such as Shor's algorithm and Simon's) that I believe, but the layman's ...
7
votes
1answer
364 views

Practical implementation of Hamiltonian Evolution

Following from this question, I tried to look at the cited article in order to simulate and solve that same problem... without success. Mainly, I still fail to understand how the authors managed to ...
5
votes
1answer
63 views

Computing of the action of the amplification operator $\mathbf Q$ over $|\Psi_i\rangle$ in the quantum amplitude amplification algorithm

$\newcommand{\Q}{\mathbf{Q}}\newcommand{\S}{\mathbf{S}}\newcommand{\A}{{\mathcal A}}\newcommand{\H}{\mathcal H}$In the quantum amplitude amplification algorithm, as explained in Brassard et al. 2000 (...
3
votes
0answers
34 views

Are there sites that allow to learn about quantum computing? [duplicate]

So, I wanted to learn about quantum computing. What should I learn and where do I start?
4
votes
0answers
109 views

Quantum SVM Algorithm Error on import

I am experimenting with some Qiskit ACQUA AI algorithms which require the following import statement: from datasets import * However, ...
7
votes
1answer
77 views

Does a fully working quantum computer solve a specific problem at varying speeds every time?

Lets say we have a fully working quantum computer. I give it a problem to solve and measure how long it takes to solve it. I repeat the process. Would it take the exact same time to solve the same ...
5
votes
1answer
52 views

Why does the quantum linear inversion algorithm allow to implement $e^{-ig(\rho)}$ efficiently using multiple copies of $\rho$?

In (Lloyd et al. 2013), the authors write (beginning of page 3) that the quantum matrix inversion techniques presented by some of the same authors in (Harrow et al. 2008) allow to efficiently ...
12
votes
1answer
229 views

What could be the possible future applications for HHL algorithm?

Note on the vocabulary: the word "hamiltonian" is used in this question to speak about hermitian matrices. The HHL algorithm seems to be an active subject of research in the field of quantum ...