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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

2
votes
1answer
11 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)...
7
votes
1answer
82 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 ...
-2
votes
0answers
41 views

Quantum Computing and Imagination [closed]

Does it appear that the notion and understanding and interpretation of the notion of quantum mechanics and machines based upon principles and ideas that have surfaced from the connection and ...
3
votes
1answer
52 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?
6
votes
2answers
50 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
60 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
146 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. ...
5
votes
2answers
170 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 ...
6
votes
1answer
161 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
189 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 ...
5
votes
2answers
103 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
101 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 ...
7
votes
2answers
92 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
75 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
22 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
53 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
74 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 ...
6
votes
1answer
318 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
55 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
32 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
76 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
69 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
43 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
207 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 ...
5
votes
1answer
69 views

Compact encoding of Boolean formula as oracle

As in the title, I have a doubt regarding the implementation of a boolean formula used as an oracle for a quantum algorithm. The problem is that so far I could reproduce the formula as a quantum ...
5
votes
2answers
66 views

HHL algorithm — problem with the outcome of postselection

See edit at the end of the question All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009). HHL algorithm ...
4
votes
1answer
158 views

HHL algorithm — controlled-by-eigenvalues rotations

All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009). The question I have is about the step where they apply ...
6
votes
1answer
335 views

When you act on a multi-qubit system with a 2-qubit gate, what happens to the third qubit?

I am learning to manipulate Qbits and recently I saw the teleportation algorithm. I read about it in two places: Wikipedia and Lecture Notes from Ronald de Wolf (Page 7, 1.5 Example: Quantum ...
4
votes
2answers
114 views

Is running a large random brute force on quantum computer possible at the moment?

I want to run a experiment like this: Generate a bunch of random 12-character passwords like $``\texttt{<Bb\{Q,r2Qp8`}".$ Write an algorithm to randomly generate & compare value on quantum ...
6
votes
1answer
133 views

Basic approximation in Solovay-Kitaev algorithm

I read the Solovay-Kitaev algorithm for approximation of arbitrary single-qubit unitaries. However, while implementing the algorithm, I got stuck with the basic approximation of depth 0 of the ...
5
votes
0answers
45 views

HHL algorithm — why isn't the required knowledge on eigenspectrum a major drawback?

This question is a continuation of Quantum phase estimation and HHL algorithm - knowledge on eigenvalues required?. In the question linked above, I asked about the necessity for HHL to have ...
8
votes
1answer
105 views

Quantum phase estimation and HHL algorithm - knowledge on eigenvalues required?

The quantum phase estimation algorithm (QPE) computes an approximation of the eigenvalue associated to a given eigenvector of a quantum gate $U$. Formally, let $\left|\psi\right>$ be an ...
8
votes
0answers
74 views

Quantum walk with binary tree

I’m trying to grok quantum walks, and would like to create an example that walks a perfect binary tree to find the one and only marked leaf node. Is this possible? If so, suppose the depth of the tree ...
2
votes
1answer
54 views

Phononic Quantum Computing

Google returns "About 1 results" for Quantum Computing with Sound. The sole result links to an article entitled "Physicists have designed the building blocks of quantum computer that works using ...
5
votes
1answer
111 views

Can quantum money be reliably “burned?”

One of the novel features of Bitcoin and other cryptocurrencies is that coins can be irrefutably "burned" or destroyed, by creating a transaction to send the money to a junk burn address. Thinking ...
-4
votes
2answers
132 views

Scale for Quantum Computing [closed]

Does something like Mohs' scale exist for quantum computing? (eg. classical=0, hybrid=5, pure quantum=10) Mohs' scale: a scale of hardness used in classifying minerals. It runs from 1 to 10 using a ...
5
votes
0answers
74 views

How exactly is the stated composite state of the two registers being produced using the $R_{zz}$ controlled rotations?

This is a sequel to How are two different registers being used as "control"? I found the following quantum circuit given in Fig 5 (page 6) of the same paper i.e. Quantum Circuit Design for ...
5
votes
1answer
103 views

Quantum Arithmetic

I'm looking at this paper and try to implement the Quantum adders they define myself. Suppose we have a number $b=b_{n-1}\dots b_1b_0$ and they want to add a constant number $a=a_{n-1}\dots a_1a_0$. ...
6
votes
1answer
82 views

How to benchmark a quantum computer?

Using a simple puzzle game to benchmark quantum computers is the most clever approach I have seen so far. The author of the aforementioned article, James, makes a nice analogy to buying a laptop ("...
8
votes
1answer
124 views

How to implement a matrix exponential in a quantum circuit?

Maybe it is a naive question, but I cannot figure out how to actually exponentiate a matrix in a quantum circuit. Assuming to have a generic square matrix A, if I want to obtain its exponential, $e^{A}...
6
votes
2answers
68 views

Construct Controlled-$G^{\dagger}$ from known Controlled-$G$

Let there be a known a scheme (quantum circuit) of Controlled-G, where unitary gate G has G$^†$ such that G≠G$^†$ and GG$^†$=I (for example S and S$^†$, T and T$^†$, V and V$^†$, but not Pauli and H ...
3
votes
1answer
128 views

Quantum algorithm to evaluate numbers in fast growing hierarchy

What quantum technologies and/or techniques (if any) could be used to evaluate the value of large numbers in the fast growing hierarchy such as Tree(3) or SCG(13)?
3
votes
1answer
78 views

Realization of Quantum Shadowgraphy

I recently found out about shadowgraphy and was wondering if a technique like this could be used to: Visually show entanglement Suffice as a measure (e.g. continous partial trace) Most useful ...
3
votes
3answers
65 views

Use of change of phase gates

As explained in this this answer, when we have different (relative) phases between two states, those two states will yield the same probabilities when measured in the same basis but different ...
6
votes
2answers
118 views

Quantum algorithm for linear systems of equations (HHL09): Step 2 - Preparation of the initial states $|\Psi_0\rangle$ and $|b\rangle$

This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$? In the paper: Quantum algorithm for linear systems of equations (Harrow, ...
8
votes
2answers
2k views

How many operations can a quantum computer perform per second?

I want to know what time complexity is considered efficient/inefficient for quantum computers. For this, I need to know how many operations a quantum computer can perform per second. Can anyone tell ...
9
votes
1answer
126 views

What kind of real world problems (excluding cryptography) can be solved efficiently by a quantum algorithm?

This question is very similar as Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer? But the answers provided to that questions mainly ...
6
votes
2answers
151 views

Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is $|\Psi_0\rangle$?

This is a sequel to Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm and Quantum algorithm for linear systems of ...
7
votes
1answer
133 views

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Number of qubits needed

This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm Questions (contd.): Part 2: I'm not exactly ...
8
votes
2answers
264 views

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm

I have been trying to get my head around the famous(?) paper Quantum algorithm for linear systems of equations (Harrow, Hassidim & Lloyd, 2009) (more popularly known as the HHL09 algorithm paper) ...