Questions tagged [adiabatic-model]
Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to do calculations and is closely related to and may be regarded as a subclass of, quantum annealing. (Wikipedia)
69
questions
2
votes
1
answer
58
views
Computational complexity of the circuit model vs adiabatic model?
I'm trying to understand how computational complexity is quantified in adiabatic quantum computing.
With the circuit model, computational complexity is simple: count the number of times you queried ...
anon
0
votes
0
answers
11
views
Can the process of adiabatic quantum optimization be simply a reverse of spontaneous synchronization?
I assume we can model a complex potential by many harmonic oscillators with many different couplings and with added to their potentials different constants so that the system has many local minima and ...
6
votes
3
answers
515
views
Can Shor's algorithm be done with the same efficiency on an adiabatic quantum computer as on a circuit-based one?
Unfortunately, I cannot find any information on this, so I am asking in this forum if anyone knows, and if so, why this is the case?
- 73
0
votes
1
answer
35
views
Adiabatic computing basics
I am reading about adiabatic quantum computing- specifically, about how it can find the lowest energy configuration of the Ising model. It is said that the initial state is a superposition of all the ...
3
votes
1
answer
108
views
Derivation of QAOA from AQC
In adiabatic quantum optimization we start with an initial Hamiltonian $H_0$ and then adiabatically evolve from $H_0$ to $H_P$ (problem hamiltonian) for a time $T$ according to
\begin{equation}\label{...
- 167
1
vote
0
answers
14
views
AQC definition modifications costs and pay-offs
I was wondering if one can think of a more general relation between alleviating conditions for the state in which the evolution takes palce in AQC paradigm and constraining the structure of the ...
0
votes
0
answers
23
views
Example Problem and/or Code for Quantum Annealing?
I have an interview with D-Wave tomorrow and want to make sure I'm prepared. Does anyone know of one or two in-depth, rigorous examples of quantum annealing that I could work through theoretically?
- 454
3
votes
0
answers
34
views
How to compare Quantum Annealing and Adiabatic Quantum Computing?
I'm still unsure on the difference between adiabatic quantum computing (AQC) and quantum annealing (QA). Please critique these interpretations:
AQC: Define a Hamiltonian with an easy-to-prepare ...
- 454
5
votes
2
answers
171
views
Under what conditions the minimum eigengap is non-zero?
I would like to know sufficient conditions for a non-zero eigengap of a time-dependent Hamiltonian.
Suppose we have a time-dependent Hamiltonian $H(t)$ defined as follows:
$$H(t) = (1-s(t))H_{init} + ...
- 2,172
7
votes
1
answer
193
views
What arguments point towards D-Wave devices being potentially useful?
I'm looking for any evidence pointing towards D-Wave's approach to quantum computation being promising to achieve any sort of computational advantage with respect to classical devices.
Note that I'm ...
glS♦
- 21.7k
1
vote
0
answers
23
views
Error analysis on the approximation of an adiabatic evolution operator by a QAOA circuit
I would like to know what would be the approximation error of a QAOA circuit.
Suppose we have time-dependent Hamiltonian $H(t) = (1 - s(t))H_{init} + s(t)H_{prob}$ where $H_{init}$ in an initial ...
- 2,172
2
votes
1
answer
95
views
Is there any rigorous proof that Quantum Annealing provides a quantum advantage?
Is there any rigorous proof that Quantum Annealing (QA) is of any benefit (e.g. in terms of time to optimal solution, convergence rate, etc.) for a specific problem? Or any empirical evidence for the ...
- 415
1
vote
2
answers
117
views
Is digital quantum computing more powerful than the analog one?
What I get so far:
Analog quantum computing:
The Hamiltonian is implemented on the QC, solution is found by e.g. quantum annealing. The whole state is changing continuously.
Digital quantum computing:
...
- 167
1
vote
0
answers
27
views
Computational Complexity of random Transverse-Ising Chain
It is well known that many NP-hard classical problems can be mapped to a spin-configuration Ising problem (see for example https://arxiv.org/pdf/1302.5843.pdf)
However, what I would like to know is ...
- 101
2
votes
0
answers
32
views
The energy levels crossover problem in Quantum Annealing
How to avoid energy levels crossover in quantum annealing by Kibble-Zurek mechanism? Any detailed references?
- 31
3
votes
1
answer
81
views
Understanding QAOA from Basics/scratch
Recently after working on QAOA with finance and graph coloring problems. I have started exploring the QAOA from scratch. I would like to understand the QAOA derivation mathematically and have started ...
- 31
4
votes
0
answers
119
views
Why does QAOA's performance monotonically increase as p increases?
From A Quantum Approximate Optimization Algorithm - Farhi et al.
The Quantum Approximate Optimization Algorithm has the key feature that as
p
increases the approximation improves. We contrast this to ...
- 249
3
votes
0
answers
32
views
Quantum Adiabatic algorithm and Hardness of ExactCover
It was numerically shown in this paper that the ExactCover problem, given the unique satisfying assignment (USA) assumption, could be solved by an adiabatic quantum algorithm (AQC) in time polynomial ...
- 51
2
votes
0
answers
119
views
How to formulate QUBO as summation quadratic and linear parts of K-graph coloring problem?
While trying to understand the graph coloring problem with VQE using the QUBO Formulation mentioned section "5.2 Graph Coloring". Mentioned article prepared the QUBO directly in to matrix ...
- 31
4
votes
0
answers
161
views
Any simulator packages for quantum annealing/adiabatic quantum computation?
Are there any simulator packages for quantum annealing/adiabatic quantum computation, like Qiskit Aer but for quantum annealing?
There seems to be only classical heuristics in D-Wave Ocean package, ...
- 166
2
votes
0
answers
66
views
Example of lower bound on spectral gap for adiabatic quantum computing
is there a list of reference for which the authors prove a lower bound of the spectral gap for an adiabatic quantum algorithm? I.e. I am searching for examples where the authors solve a problem with ...
- 493
1
vote
1
answer
175
views
How is eigendecomposition of a Hamiltonian equivalent to finding the minimum of an energy function?
This question is in regards to Dwave's quantum computer which is tailored to solve QUBO problems using quantum annealing.
QM tells us that the ground state of a quantum system is given by the ...
- 349
3
votes
1
answer
88
views
Comparing complexity of digital and analog quantum computation
The complexity of an algorithm run on a digital quantum computer is quantified, roughly, by the number of elementary gates in the corresponding circuit. Can one similarly quantify the complexity of an ...
- 1,375
1
vote
1
answer
69
views
Question about the counter diabatic(CD) term in Digitized Adiabatic Quantum Computing
Recently I have read two articles about the Digitized Adiabatic Quantum Computing(DAQC), and tried to factorize $35=5\times7$ and $2479=67\times37$.
But some problems came when trying to solve the ...
- 21
1
vote
1
answer
98
views
Standard to select base hamiltonaian for Adiabatic quantum computing
I'm learning about connection between QUBO and The Ising Model.
It says
Take the base Hamiltonian of an adiabatic process as $\sum_i \big(\frac{1-\sigma_i^x}{2}\big)$
to implement Hamiltonian for ...
- 75
1
vote
2
answers
134
views
The Adiabatic Theorem - How to derive Schrödinger equation in the "s" variable
I'm studying Adiabatic Quantum computing from the book
"Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice" by Catherine C. McGeoch at D-Wave.
The section THE ...
- 143
1
vote
0
answers
60
views
Penalty Function for XOR gate
I was reading a paper on Gates for Adiabatic Quantum Computer. In the paper, there were different penalty functions already given in the form of the following table:
I do not quite understand the ...
- 33
3
votes
1
answer
106
views
Relationship of Adiabatic Quantum Computing speedup to Quantum Random Walk hit time
Considering the following two phenomena:
Adiabatic quantum computing in general exhibits a quadratic speedup over classical simulated annealing, though for some Hamiltonians it may be faster (while ...
- 397
4
votes
2
answers
135
views
Why is it so important to have uniform chain lengths in a minor embedding?
Very brief background
In quantum annealing, the discrete optimization problem we wish to solve (such as finding the minimum of $b_1b_2 - 3b_1 + 5b_3b_4$ for binary variables $b_i$) may have a ...
- 12.8k
7
votes
1
answer
252
views
Why do I get this extra factor when working out the dynamics of an adiabatic quantum computation?
I was trying to revise my understanding of adiabatic quantum computation via a simple example. I'm familiar with the overall concept -- that you have an overall Hamiltonian
$$
H(s)=(1-s)H_0+s H_f
$$
...
- 52.3k
6
votes
2
answers
790
views
Why is the time ordering omitted in the trotterised version of the time-dependent evolution operator?
The unitary evolution of a time-dependent hamiltonian is given by the time-ordered matrix exponential
$$\begin{aligned}
U(t)&=\mathcal T\exp\left[-i\int_0^tH(\tau)d\tau\right]\\
&=I-i\int_0^td\...
8
votes
3
answers
523
views
In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?
X-posted on physics.stackexchange
In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic speedup ...
2
votes
1
answer
177
views
Adiabatic Quantum Computer e intermediate Hamiltonian evolves the state within the manifold
The Adiabatic Quantum Computer is implemented by slowly increasing the parameter s from 0 to 1 in the intermediate Hamiltonian $[\hat{H}(s) = \hat{H}_{input} + (1-s)\hat{H}_{init} + s\hat{H}_{circuit}]...
- 515
0
votes
0
answers
58
views
Types of Quantum Computer [duplicate]
I am confused of all that different Quantum computers.
please correct me if I say something wrong.
There are two main different types of quantum computing:
Quantum Gates based computing
quantum ...
- 141
3
votes
0
answers
66
views
Is the problem Hamiltonian in QAOA and AQC always a phase Hamiltonian?
In QAOA and AQC the problem Hamiltonian is always a Phase Hamiltonian (meaning only phases are added)
Is that part of the QAOA and AQC definition or it is only used because it is convenient and work?
...
- 519
9
votes
3
answers
527
views
What is the computational complexity of quantum annealing?
Quantum annealing can be thought of as a black box solver that can find approximate solutions to hard optimization problems. For example, D-Wave quantum annealers can approximately solve quadratic ...
6
votes
1
answer
264
views
Why QAOA with $p \rightarrow \infty $ gives the optimal solution?
In the QAOA paper, it is shown that the optimal value of the p-ansatz $M_p$ converges to $\max_z C(z)$ as $p \rightarrow \infty$ on page 10. The proof is to relate to QAOA by considering the time-...
- 291
2
votes
1
answer
228
views
Why does the problem Hamiltonian of QAOA always consist of $Z$ and $I$ gates?
I noticed that in QAOA the problem hamiltonian always consists of $Z$ and $I$ gates. But isn't QAOA a form of Adiabatic Programming? Where the idea is just to go from one ground state to another?
Does ...
- 519
8
votes
1
answer
1k
views
What is known about quantum algorithms for graph isomorphism?
Shor's algorithm (for factoring integers) and Grover's algorithm (for searches) are the two most well-known quantum algorithms. I was wondering if there was a similar result in QC that dealt with the ...
- 211
3
votes
2
answers
110
views
The commutation relation $[H_d, \sum_{i = 1}^n \sigma_i^z] = 0$ from the paper about the constrained quantum annealing (CQA)
A quote from the paper "Quantum annealing for constrained optimization" by I. Hen, F. M. Spedalieri:
Let us now consider the driver Hamiltonian
$$H_d = - \sum_{i=1}^n \left( \sigma_i^x \...
- 4,146
1
vote
0
answers
135
views
Is the Elitzur-Vaidman bomb tester an example of adiabatic evolution?
I'm trying to grok more of the adiabatic model. I also really enjoyed O'Donnell's lecture on the Elitzur-Vaidman bomb tester.
The familiar setup involves a test for the presence (or absence) of a ...
- 9,346
4
votes
0
answers
71
views
Is either the adiabatic or the diabatic version of quantum annealing known to be theoretically more powerful than the other?
Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "...
- 2,357
1
vote
1
answer
47
views
Books about the measurement for Hamiltonian Energy
I am searching for articles/books about the measurement energy of Hamiltonians in adiabatic quantum computing. Do you know of any good resources?
- 121
1
vote
0
answers
49
views
Is it absolutely necessary for Hamiltonians to not commute in QAA?
I have already read through the answers here.
So I understand that if the Hamiltonians commute, then they have the same eigenstates but not necessarily the same energy eigenvalues.
To formulate my ...
- 616
3
votes
2
answers
1k
views
What is an example of a simple QUBO problem?
I am digging into to the workings of the D-wave quantum annealing computers using this documentation. I find it very intuitive and well-explained, but their example of a "simple QUBO problem"...
- 151
2
votes
0
answers
54
views
van Dam's proof for adiabatic optimization and graph diameter
My question concerns a proof in https://people.eecs.berkeley.edu/~vazirani/pubs/qao.pdf, "Limits on Quantum Adiabatic Optimization - Warning: Rough Manuscript!" by Wim van Dam and Umesh Vazirani. It ...
- 311
3
votes
0
answers
23
views
Can we speed up the adiabatic process if we split the target hamiltonian in commuting parts?
$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$
...
- 628
5
votes
1
answer
91
views
How to tell if the ground states of two Hamiltonians are solutions of the same optimization problem?
Let's say, that we have an optimization problem in the form:
$$ \min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,
$$
where $f(x)$ is an objective function, $g_i(x)$ are ...
- 1,019
12
votes
1
answer
875
views
Is there a general method of expressing optimization problem as a Hamiltonian?
Let's say, that we have an optimization problem in the form:
$$ \min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,
$$
where $f(x)$ is an objective function, $g_i(x)$ are ...
- 1,019
4
votes
2
answers
418
views
How to recognize if a paper is talking about quantum annealing or gate logic?
I am currently reading various survey papers in Quantum Machine Learning, such as "Quantum Machine Learning" by Biamonte, Wittek, Pancotti, Rebentrost, Wiebe, and Lloyd. To me, it is not clear when ...
