How to describe, or encode, the input vector x of Quantum Fourier Transform?
up vote
5
down vote
favorite
Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT.
I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains something important between classical and quantum Fourier Transform.
Inside 1, it describes that:
The quantum Fourier transform is based on essentially the same idea with the only difference that the vectors x and y are state vectors (see formula 5.2, 5.3),
However, I couldn't catch up the statement regarding "x and y are state vectors"; I get stuck at the formula 5.2 and 5.3.
I want to know how to convert the classical input vector x to the right hand side of the formula 5.2.
If this confusing problem is solved, it'll be better for me to understand the time complexity issue of QFT.
algorithm quantum-fourier-transform
edited Nov 20 at 14:01
Blue♦
5,64011352
asked Nov 20 at 9:25
user3176354
283
add a comment |
up vote
5
down vote
favorite
Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT.
I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains something important between classical and quantum Fourier Transform.
Inside 1, it describes that:
The quantum Fourier transform is based on essentially the same idea with the only difference that the vectors x and y are state vectors (see formula 5.2, 5.3),
However, I couldn't catch up the statement regarding "x and y are state vectors"; I get stuck at the formula 5.2 and 5.3.
I want to know how to convert the classical input vector x to the right hand side of the formula 5.2.
If this confusing problem is solved, it'll be better for me to understand the time complexity issue of QFT.
algorithm quantum-fourier-transform
edited Nov 20 at 14:01
Blue♦
5,64011352
asked Nov 20 at 9:25
user3176354
283
2
Related: Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
– Blue♦
Nov 20 at 13:32
add a comment |
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT.
I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains something important between classical and quantum Fourier Transform.
Inside 1, it describes that:
The quantum Fourier transform is based on essentially the same idea with the only difference that the vectors x and y are state vectors (see formula 5.2, 5.3),
However, I couldn't catch up the statement regarding "x and y are state vectors"; I get stuck at the formula 5.2 and 5.3.
I want to know how to convert the classical input vector x to the right hand side of the formula 5.2.
If this confusing problem is solved, it'll be better for me to understand the time complexity issue of QFT.
algorithm quantum-fourier-transform
edited Nov 20 at 14:01
Blue♦
5,64011352
asked Nov 20 at 9:25
user3176354
283
Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT.
I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains something important between classical and quantum Fourier Transform.
Inside 1, it describes that:
The quantum Fourier transform is based on essentially the same idea with the only difference that the vectors x and y are state vectors (see formula 5.2, 5.3),
However, I couldn't catch up the statement regarding "x and y are state vectors"; I get stuck at the formula 5.2 and 5.3.
I want to know how to convert the classical input vector x to the right hand side of the formula 5.2.
If this confusing problem is solved, it'll be better for me to understand the time complexity issue of QFT.
algorithm quantum-fourier-transform
algorithm quantum-fourier-transform
edited Nov 20 at 14:01
Blue♦
5,64011352
asked Nov 20 at 9:25
user3176354
283
edited Nov 20 at 14:01
Blue♦
5,64011352
asked Nov 20 at 9:25
user3176354
283
edited Nov 20 at 14:01
Blue♦
5,64011352
edited Nov 20 at 14:01
Blue♦
5,64011352
edited Nov 20 at 14:01
Blue♦
5,64011352
5,64011352
asked Nov 20 at 9:25
user3176354
283
asked Nov 20 at 9:25
user3176354
283
asked Nov 20 at 9:25
user3176354
283
283
2
Related: Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
– Blue♦
Nov 20 at 13:32
add a comment |
2
Related: Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
– Blue♦
Nov 20 at 13:32
2
2
Related: Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
– Blue♦
Nov 20 at 13:32
Related: Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
– Blue♦
Nov 20 at 13:32
add a comment |
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state.
This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum algorithms using this encoding we can achieve exponential speedup in the size of the problem.
However, generally in quantum computing, you have to assume that this encoding is done using a device called quantum random access memory for loading in this form a vector. Or you are given a circuit that do the job for you.
answered Nov 20 at 9:55
cnada
1,699211
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
add a comment |
up vote
4
down vote
You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve this in polynomial time.
answered Nov 20 at 9:53
Norbert Schuch
1,188211
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "694"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4769%2fhow-to-describe-or-encode-the-input-vector-x-of-quantum-fourier-transform%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state.
This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum algorithms using this encoding we can achieve exponential speedup in the size of the problem.
However, generally in quantum computing, you have to assume that this encoding is done using a device called quantum random access memory for loading in this form a vector. Or you are given a circuit that do the job for you.
answered Nov 20 at 9:55
cnada
1,699211
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
add a comment |
up vote
3
down vote
accepted
Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state.
This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum algorithms using this encoding we can achieve exponential speedup in the size of the problem.
However, generally in quantum computing, you have to assume that this encoding is done using a device called quantum random access memory for loading in this form a vector. Or you are given a circuit that do the job for you.
answered Nov 20 at 9:55
cnada
1,699211
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
add a comment |
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state.
This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum algorithms using this encoding we can achieve exponential speedup in the size of the problem.
However, generally in quantum computing, you have to assume that this encoding is done using a device called quantum random access memory for loading in this form a vector. Or you are given a circuit that do the job for you.
answered Nov 20 at 9:55
cnada
1,699211
Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state.
This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum algorithms using this encoding we can achieve exponential speedup in the size of the problem.
However, generally in quantum computing, you have to assume that this encoding is done using a device called quantum random access memory for loading in this form a vector. Or you are given a circuit that do the job for you.
answered Nov 20 at 9:55
cnada
1,699211
edited Nov 20 at 11:10
answered Nov 20 at 9:55
cnada
1,699211
answered Nov 20 at 9:55
cnada
1,699211
answered Nov 20 at 9:55
cnada
1,699211
1,699211
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
add a comment |
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
Thank you for your answer. I'm not sure if your answer contradicts with Norbert's(the other answer). Or maybe both of you are saying the same thing but I cannot see through it..........
– user3176354
Nov 20 at 10:41
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
@user3176354 It does not. When I say "a circuit that does the job for you", a circuit is also an algorithm whose output is the state x. Formula 5.2 is typical of an amplitude encoding done by QRAM, which will create this preparation by applying a circuit for this purpose. The purpose of the QRAM will be to prepare classical data to quantum form (however we do not have an efficient implementation of such device so far).
– cnada
Nov 20 at 11:09
add a comment |
up vote
4
down vote
You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve this in polynomial time.
answered Nov 20 at 9:53
Norbert Schuch
1,188211
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
add a comment |
up vote
4
down vote
You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve this in polynomial time.
answered Nov 20 at 9:53
Norbert Schuch
1,188211
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
add a comment |
up vote
4
down vote
up vote
4
down vote
You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve this in polynomial time.
answered Nov 20 at 9:53
Norbert Schuch
1,188211
You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve this in polynomial time.
answered Nov 20 at 9:53
Norbert Schuch
1,188211
answered Nov 20 at 9:53
Norbert Schuch
1,188211
answered Nov 20 at 9:53
Norbert Schuch
1,188211
answered Nov 20 at 9:53
Norbert Schuch
1,188211
1,188211
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
add a comment |
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
Thank you for your answer. But I'm still confused; according to the referenced pdf/website, the author says something between formula 5.3 and 5.4 in a way that makes want to think that we convert a classical input to the r.h.s. of Eq. (5.2). What the author says between formula 5.3 and 5.4 is " Then the action on the components of state vector x is described by 5.1 so that".
– user3176354
Nov 20 at 10:38
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
@user3176354 In the formulation you quote, there is nothing saying that this is converted to classical.
– Norbert Schuch
Nov 20 at 12:36
add a comment |
Thanks for contributing an answer to Quantum Computing Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4769%2fhow-to-describe-or-encode-the-input-vector-x-of-quantum-fourier-transform%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Related: Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?
– Blue♦
Nov 20 at 13:32