[math-fun] quantum computers "1000s of times faster"?
I wonder what this meant? It is very mysterious: https://www.amherst.edu/aboutamherst/news/faculty/node/466477 I failed to find any actual paper this was based on, but she gave a lecture, and here is the advert for the lecture: ========= I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software) for solving NP-hard combinatorial optimization problems. This unusual computing platform is manufactured by D-Wave Systems of Burnaby, Canada. It comprises a Linux front end with an analog hardware chip that contains up to 512 quantum bits (qubits) capable of quantum superposition. The hardware chip solves optimization problems by a process known as quantum annealing (QA), based on the principles of adiabatic quantum computation (AQC). Performance comparisons included three conventional solvers-- IBM CPLEX, an open-source implementation of Tabu Search and a branch-and-bound solver that performed well in a recent satisfiability competition. The solvers were tested using instances from three NP-hard optimization problems: Quadratic Unconstrained Boolean Optimization (QUBO), Weighted Max 2-SAT (W2SAT) and the Quadratic Assignment Problem (QAP). On general problems, the hybrid software/quantum hardware solver was competitive with, and sometimes outperformed, the conventional solvers. On "native" instances that can be solved directly in hardware, the quantum system found optimal solutions 3,000 times faster than CPLEX. (Recent tests on a newer chip suggest that speedup factors of 10,000 or more are possible.) I will also describe some tests to learn how performance of the quantum hardware depends on input properties. This is joint work with Cong Wang of Simon Fraser University. --end. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
This seems more like the improvement I'd expect from an ASIC than from a quantum computer. But in any case quantum computers are not known or believed to be able to solve NP-complete problems in polynomial time. Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, May 8, 2013 at 4:40 PM, Warren D Smith <warren.wds@gmail.com> wrote:
I wonder what this meant? It is very mysterious:
https://www.amherst.edu/aboutamherst/news/faculty/node/466477
I failed to find any actual paper this was based on, but she gave a lecture, and here is the advert for the lecture: =========
I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software) for solving NP-hard combinatorial optimization problems.
This unusual computing platform is manufactured by D-Wave Systems of Burnaby, Canada. It comprises a Linux front end with an analog hardware chip that contains up to 512 quantum bits (qubits) capable of quantum superposition. The hardware chip solves optimization problems by a process known as quantum annealing (QA), based on the principles of adiabatic quantum computation (AQC).
Performance comparisons included three conventional solvers-- IBM CPLEX, an open-source implementation of Tabu Search and a branch-and-bound solver that performed well in a recent satisfiability competition. The solvers were tested using instances from three NP-hard optimization problems: Quadratic Unconstrained Boolean Optimization (QUBO), Weighted Max 2-SAT (W2SAT) and the Quadratic Assignment Problem (QAP).
On general problems, the hybrid software/quantum hardware solver was competitive with, and sometimes outperformed, the conventional solvers. On "native" instances that can be solved directly in hardware, the quantum system found optimal solutions 3,000 times faster than CPLEX. (Recent tests on a newer chip suggest that speedup factors of 10,000 or more are possible.)
I will also describe some tests to learn how performance of the quantum hardware depends on input properties.
This is joint work with Cong Wang of Simon Fraser University. --end.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's an interesting article on D-Wave written by Scott Aaronson http://www.scottaaronson.com/blog/?p=954 On Wed, May 8, 2013 at 2:07 PM, Charles Greathouse < charles.greathouse@case.edu> wrote:
This seems more like the improvement I'd expect from an ASIC than from a quantum computer. But in any case quantum computers are not known or believed to be able to solve NP-complete problems in polynomial time.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, May 8, 2013 at 4:40 PM, Warren D Smith <warren.wds@gmail.com> wrote:
I wonder what this meant? It is very mysterious:
https://www.amherst.edu/aboutamherst/news/faculty/node/466477
I failed to find any actual paper this was based on, but she gave a lecture, and here is the advert for the lecture: =========
I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software) for solving NP-hard combinatorial optimization problems.
This unusual computing platform is manufactured by D-Wave Systems of Burnaby, Canada. It comprises a Linux front end with an analog hardware chip that contains up to 512 quantum bits (qubits) capable of quantum superposition. The hardware chip solves optimization problems by a process known as quantum annealing (QA), based on the principles of adiabatic quantum computation (AQC).
Performance comparisons included three conventional solvers-- IBM CPLEX, an open-source implementation of Tabu Search and a branch-and-bound solver that performed well in a recent satisfiability competition. The solvers were tested using instances from three NP-hard optimization problems: Quadratic Unconstrained Boolean Optimization (QUBO), Weighted Max 2-SAT (W2SAT) and the Quadratic Assignment Problem (QAP).
On general problems, the hybrid software/quantum hardware solver was competitive with, and sometimes outperformed, the conventional solvers. On "native" instances that can be solved directly in hardware, the quantum system found optimal solutions 3,000 times faster than CPLEX. (Recent tests on a newer chip suggest that speedup factors of 10,000 or more are possible.)
I will also describe some tests to learn how performance of the quantum hardware depends on input properties.
This is joint work with Cong Wang of Simon Fraser University. --end.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
Beware quantum con men. Brent Meeker On 5/8/2013 1:40 PM, Warren D Smith wrote:
I wonder what this meant? It is very mysterious:
https://www.amherst.edu/aboutamherst/news/faculty/node/466477
I failed to find any actual paper this was based on, but she gave a lecture, and here is the advert for the lecture: =========
I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software) for solving NP-hard combinatorial optimization problems.
This unusual computing platform is manufactured by D-Wave Systems of Burnaby, Canada. It comprises a Linux front end with an analog hardware chip that contains up to 512 quantum bits (qubits) capable of quantum superposition. The hardware chip solves optimization problems by a process known as quantum annealing (QA), based on the principles of adiabatic quantum computation (AQC).
Performance comparisons included three conventional solvers-- IBM CPLEX, an open-source implementation of Tabu Search and a branch-and-bound solver that performed well in a recent satisfiability competition. The solvers were tested using instances from three NP-hard optimization problems: Quadratic Unconstrained Boolean Optimization (QUBO), Weighted Max 2-SAT (W2SAT) and the Quadratic Assignment Problem (QAP).
On general problems, the hybrid software/quantum hardware solver was competitive with, and sometimes outperformed, the conventional solvers. On "native" instances that can be solved directly in hardware, the quantum system found optimal solutions 3,000 times faster than CPLEX. (Recent tests on a newer chip suggest that speedup factors of 10,000 or more are possible.)
I will also describe some tests to learn how performance of the quantum hardware depends on input properties.
This is joint work with Cong Wang of Simon Fraser University. --end.
Their tongues might not be forked, but they are in superposition... At 03:01 PM 5/8/2013, meekerdb wrote:
Beware quantum con men.
Brent Meeker
On 5/8/2013 1:40 PM, Warren D Smith wrote:
I wonder what this meant? It is very mysterious:
https://www.amherst.edu/aboutamherst/news/faculty/node/466477
I failed to find any actual paper this was based on, but she gave a lecture, and here is the advert for the lecture: =========
I will describe experiments to evaluate the performance of a quantum computing system (hardware plus software) for solving NP-hard combinatorial optimization problems.
This unusual computing platform is manufactured by D-Wave Systems of Burnaby, Canada. It comprises a Linux front end with an analog hardware chip that contains up to 512 quantum bits (qubits) capable of quantum superposition. The hardware chip solves optimization problems by a process known as quantum annealing (QA), based on the principles of adiabatic quantum computation (AQC).
Performance comparisons included three conventional solvers-- IBM CPLEX, an open-source implementation of Tabu Search and a branch-and-bound solver that performed well in a recent satisfiability competition. The solvers were tested using instances from three NP-hard optimization problems: Quadratic Unconstrained Boolean Optimization (QUBO), Weighted Max 2-SAT (W2SAT) and the Quadratic Assignment Problem (QAP).
On general problems, the hybrid software/quantum hardware solver was competitive with, and sometimes outperformed, the conventional solvers. On "native" instances that can be solved directly in hardware, the quantum system found optimal solutions 3,000 times faster than CPLEX. (Recent tests on a newer chip suggest that speedup factors of 10,000 or more are possible.)
I will also describe some tests to learn how performance of the quantum hardware depends on input properties.
This is joint work with Cong Wang of Simon Fraser University. --end.
participants (5)
-
Charles Greathouse -
Henry Baker -
meekerdb -
Thane Plambeck -
Warren D Smith