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)

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
devoted4gainz's user avatar
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?
BootBootBoot's user avatar
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 ...
random person's user avatar
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{...
nuemlouno's user avatar
  • 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 ...
devoted4gainz's user avatar
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?
Ken Robbins's user avatar
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 ...
Ken Robbins's user avatar
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} + ...
MonteNero's user avatar
  • 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's user avatar
  • 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 ...
MonteNero's user avatar
  • 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 ...
Nepomuk Hirsch's user avatar
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: ...
nuemlouno's user avatar
  • 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 ...
GiannisKol's user avatar
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?
finely's user avatar
  • 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 ...
anonymousKet's user avatar
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 ...
bubakazouba's user avatar
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 ...
quantumrock's user avatar
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 ...
Ket's user avatar
  • 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, ...
haoyu's user avatar
  • 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 ...
asdf's user avatar
  • 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 ...
morpheus's user avatar
  • 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 ...
Nikita Nemkov's user avatar
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 ...
Liu's user avatar
  • 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 ...
hongildong1's user avatar
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 ...
Prksa's user avatar
  • 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 ...
Srijan's user avatar
  • 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 ...
Sideshow Bob's user avatar
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 ...
user1271772's user avatar
  • 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 $$ ...
DaftWullie's user avatar
  • 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\...
Dyon J Don Kiwi van Vreumingen's user avatar
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 ...
Hans-Ulrich Rudel's user avatar
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}]...
heromano's user avatar
  • 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 ...
Jeff24's user avatar
  • 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? ...
Hannah's user avatar
  • 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 ...
Dr. Prasanna Date's user avatar
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-...
John Wong's user avatar
  • 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 ...
Hannah's user avatar
  • 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 ...
paulinho's user avatar
  • 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 \...
Davit Khachatryan's user avatar
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 ...
Mark Spinelli's user avatar
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 "...
tparker's user avatar
  • 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?
Blabla's user avatar
  • 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 ...
Alexander Soare's user avatar
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"...
Thomas Wagenaar's user avatar
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 ...
Alex Meiburg's user avatar
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>}$ ...
draks ...'s user avatar
  • 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 ...
brzepkowski's user avatar
  • 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 ...
brzepkowski's user avatar
  • 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 ...
Thomas Hubregtsen's user avatar