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)
83
questions
3
votes
3
answers
156
views
Does optimization via Hamiltonian evolution have an analogy like gradient descent?
I'm trying to find out, if there is a simplified concept to understand what is occuring during quantum annealing/ Falqon/ Hamiltonian evolution like algorithms.
During classical gradient descent ...
- 361
2
votes
1
answer
57
views
Complexity of minor embedding [closed]
I am looking for a proof why the minor embedding problem (or minor graph search or minor testing) belongs to NP-complete problems.
I would like to find a paper or in general an explanation that shows ...
1
vote
0
answers
33
views
Adiabatic evolution vs QAOA
Attempting to understand some basics here before
developing an quantum algorithm.
Would of you be able to help clarify the
following definitions I attempted to construct
which compare the two ...
- 11
1
vote
0
answers
32
views
How to approximate the time-dependent Hamiltonian in quantum adiabatic theory by the non time-dependent Hamiltonian?
Recently, I am learning how to solve the linear equation $A\left | x \right \rangle =\left | b \right \rangle $ using quantum adiabatic theory. In the solving process, people usually need to set the ...
- 11
1
vote
1
answer
70
views
How to actually solve for the eigenstates in the adiabatic version of Grover's algorithm
The adiabatic version of Grover's algorithm says that the eigenstates of the Hamiltonian $H(t)=(1-\frac{t}{T})H_0+\frac{t}{T}H_m$ (equation 10 in the linked paper) can be used to solve the eigenvalue ...
- 175
2
votes
0
answers
43
views
Derivation of energy gap formula for adiabatic Grover algorithm
I am having a difficulty in finding the full derivation for local search energy gap, as described in In the adiabatic version of Grover's algorithm, how is the Hamiltonian constructed?. I looked ...
- 457
2
votes
0
answers
27
views
Can adiabatic quantum computing be used to find local minimum instead of ground states?
We know that with unfriendly energy gap circumstances, adiabatic quantum computing takes exponential time to find a ground state of some hamiltonian. But if some local minimum state is all we look for,...
- 457
3
votes
0
answers
61
views
Understanding circuit to Hamiltonian embedding where we do not have a separate clock register
I am trying to understand the clock construction given in this paper, to embed a circuit to a Hamiltonian, which doesn't need to access a separate clock register.
The construction, at a high level, ...
- 1,435
4
votes
1
answer
858
views
Does the D-Wave hardware show any advantage for academic use-cases, for example in condensed matter physics?
The D-Wave team put out a few papers (like this one and this one) in the last few years describing how their methods can find ground states of certain spin-glass Hamiltonians faster than classical ...
- 1,926
20
votes
2
answers
3k
views
Did D-Wave show quantum advantage in 2023?
I would like to know your thoughts on whether or not D-Wave has shown a a smoking-gun example of quantum advantage this year. I am genuinely not quite sure what to think, but I believe the answer to ...
- 1,926
3
votes
1
answer
84
views
Python code for D-Wave Annealer
In the below screenshot, I am aware of resolving the issue by reducing num_reads as the annealing time is exceeding my allowance. Although it works, my question ...
- 241
3
votes
0
answers
119
views
Adiabatic state preparation for quantum phase estimation
I'm trying to understand the problem of state preparation for quantum phase estimation (QPE). Specifically how states are prepared adiabatically.
I have a couple of questions:
1). Typically when one ...
- 31
3
votes
0
answers
37
views
Compiling pulses with time dependent $\sigma_x$ and $\sigma_y$ control
I have a Hamiltonian of the form:
$$
H = c_x(t) \sigma_x + c_y(t) \sigma_y$$
and I want to compile a pulse "P" that has both $\sigma_x$ and $\sigma_y$ control, with different time dependent ...
- 31
2
votes
0
answers
54
views
Implementing Adiabatic Grover Search via QAOA
I am reading the paper Grover Search Inspired Alternating Operator Ansatz of Quantum Approximate
Optimization Algorithm for Search Problems. The paper proposes running the Adiabatic Grover Search ...
- 191
0
votes
2
answers
190
views
Is there a quantum algorithm for the closest vector problem on a 2-dimensional lattice?
Is there a standard quantum algorithm (adiabatic or density matrix based) that can output the answer to a 2-dimensional closest vector problem:
ie. find the closest lattice point (the blue one) that ...
- 511
1
vote
0
answers
76
views
Link between AQC and QAOA
I try to understand precisely the link between AQC and QAOA, through the Trotter-Suzuki formula.
A similar question is Derivation of QAOA from AQC, but I was asked by moderators to post my question ...
- 321
3
votes
1
answer
106
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
6
votes
3
answers
620
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?
- 93
0
votes
1
answer
47
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 ...
4
votes
1
answer
297
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{...
- 177
2
votes
0
answers
21
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 ...
5
votes
0
answers
42
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 ...
- 474
5
votes
2
answers
195
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} + ...
- 3,191
7
votes
1
answer
329
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♦
- 26.4k
1
vote
0
answers
42
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 ...
- 3,191
3
votes
1
answer
215
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 ...
- 495
1
vote
2
answers
231
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:
...
- 177
2
votes
0
answers
38
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 ...
- 131
2
votes
0
answers
38
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
179
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
194
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 ...
- 271
4
votes
0
answers
49
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 ...
- 61
2
votes
0
answers
213
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
276
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, ...
- 176
2
votes
0
answers
77
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 ...
- 503
2
votes
1
answer
279
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 ...
- 391
4
votes
1
answer
139
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,665
1
vote
1
answer
102
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
170
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
192
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
2
votes
0
answers
78
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 ...
- 43
4
votes
1
answer
135
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 ...
- 427
4
votes
2
answers
245
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 ...
7
votes
1
answer
267
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
$$
...
- 60.8k
9
votes
2
answers
1k
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
794
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
191
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}]...
- 535
0
votes
0
answers
60
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
82
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?
...
- 529
10
votes
3
answers
1k
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 ...
