Jump to content
View in the app

A better way to browse. Learn more.

Surly Horns

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

18yo UT Student Just Kicked Quantum Computing In The Ballz

Featured Replies

 

Tang seems like he’s a great guy, but there’s no chance this guy fucks.

 

https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/

 

A teenager from Texas has taken quantum computing down a notch. In a paper posted online earlier this month, 18-year-old Ewin Tang proved that ordinary computers can solve an important computing problem with performance potentially comparable to that of a quantum computer.

In its most practical form, the “recommendation problem” relates to how services like Amazon and Netflix determine which products you might like to try. Computer scientists had considered it to be one of the best examples of a problem that’s exponentially faster to solve on quantum computers — making it an important validation of the power of these futuristic machines. Now Tang has stripped that validation away.

“This was one of the most definitive examples of a quantum speedup, and it’s no longer there,” said Tang, who graduated from the University of Texas, Austin, in spring and will begin a Ph.D. at the University of Washington in the fall.

In 2014, at age 14 and after skipping the fourth through sixth grades, Tang enrolled at UT Austin and majored in mathematics and computer science. In the spring of 2017 Tang took a class on quantum information taught by Scott Aaronson, a prominent researcher in quantum computing. Aaronson recognized Tang as an unusually talented student and offered himself as adviser on an independent research project. Aaronson gave Tang a handful of problems to choose from, including the recommendation problem. Tang chose it somewhat reluctantly.

“I was hesitant because it seemed like a hard problem when I looked at it, but it was the easiest of the problems he gave me,” Tang said.

The recommendation problem is designed to give a recommendation for products that users will like. Consider the case of Netflix. It knows what films you’ve watched. It knows what all of its other millions of users have watched. Given this information, what are you likely to want to watch next?

You can think of this data as being arranged in a giant grid, or matrix, with movies listed across the top, users listed down the side, and values at points in the grid quantifying whether, or to what extent, each user likes each film. A good algorithm would generate recommendations by quickly and accurately recognizing similarities between movies and users and filling in the blanks in the matrix.

In 2016 the computer scientists Iordanis Kerenidis and Anupam Prakash published a quantum algorithm that solved the recommendation problem exponentially faster than any known classical algorithm. They achieved this quantum speedup in part by simplifying the problem: Instead of filling out the entire matrix and identifying the single best product to recommend, they developed a way of sorting users into a small number of categories — do they like blockbusters or indie films? — and sampling the existing data in order to generate a recommendation that was simply good enough.

At the time of Kerenidis and Prakash’s work, there were only a few examples of problems that quantum computers seemed to be able to solve exponentially faster than classical computers. Most of those examples were specialized — they were narrow problems designed to play to the strengths of quantum computers (these include the “forrelation” problem Quanta covered earlier this year). Kerenidis and Prakash’s result was exciting because it provided a real-world problem people cared about where quantum computers outperformed classical ones.

“To my sense it was one of the first examples in machine learning and big data where we showed quantum computers can do something that we still don’t know how to do classically,” said Kerenidis, a computer scientist at the Research Institute on the Foundations of Computer Science in Paris.

Kerenidis and Prakash proved that a quantum computer could solve the recommendation problem exponentially faster than any known algorithm, but they didn’t prove that a fast classical algorithm couldn’t exist. So when Aaronson began working with Tang in 2017, that was the question he posed — prove there is no fast classical recommendation algorithm, and thereby confirm Kerenidis and Prakash’s quantum speedup is real.

“That seemed to me like an important ‘t’ to cross to complete this story,” said Aaronson, who believed at the time that no fast classical algorithm existed.

Tang set to work in the fall of 2017, intending for the recommendation problem to serve as a senior thesis. For several months Tang struggled to prove that a fast classical algorithm was impossible. As time went on, Tang started to think that maybe such an algorithm was possible after all.

“I started believing there is a fast classical algorithm, but I couldn’t really prove it to myself because Scott seemed to think there wasn’t one, and he was the authority,” Tang said.

Finally, with the senior thesis deadline bearing down, Tang wrote to Aaronson and admitted a growing suspicion: “Tang wrote to me saying, actually, ‘I think there is a fast classical algorithm,’” Aaronson said.

Throughout the spring Tang wrote up the results and worked with Aaronson to clarify some steps in the proof. The fast classical algorithm Tang found was directly inspired by the fast quantum algorithm Kerenidis and Prakash had found two years earlier. Tang showed that the kind of quantum sampling techniques they used in their algorithm could be replicated in a classical setting. Like Kerenidis and Prakash’s algorithm, Tang’s algorithm ran in polylogarithmic time — meaning the computational time scaled with the logarithm of characteristics like the number of users and products in the data set — and was exponentially faster than any previously known classical algorithm.

Once Tang had completed the algorithm, Aaronson wanted to be sure it was correct before releasing it publicly. “I was still nervous that once Tang put the paper online, if it’s wrong, the first big paper of [Tang’s] career would go splat,” Aaronson said.

 

I hoped he uploaded his quantum algorithm on the blockchain because it has potential to be a disruptor.

I hope he sent a jar of Tang to the quantum researchers he punked.  It would be a great calling card.   Tang motherfucker!

The answer to every recommendation is porn. 

Where do I collect my prize?

Edited by Orange^White

But it's quantum computing?  Don't you get it?  It says right here on the box!  Normal PCs don't have that!

I'll take "Teenagers that make me feel stupid" for $800 Alex.

is this not very similar to the algorithms they've developed for predictive text? 

I just finished reading Origin by Dan Brown, so this hits close to home. 

Way to go Tang.  Crazy fucker was one of my pledge bros.  Delts Rule!!!!!

You've lost that log a rhythm, wo-woah that log a rhythm
You've lost that log a rhythm
'Cause of Tang, Tang, Tang

Woah woh a woah

Edited by El Diablo

1 hour ago, PW119 said:

Way to go Tang.  Crazy fucker was one of my pledge bros.  Delts Rule!!!!!

latest?cb=20110126054102

1 hour ago, RollLeft said:

Way to go Chang!

46774831-36d1-44a3-9b34-6a6fd4879da1_scr

how’s the tennis season goin?

Does any of this mean i’ll get better recommendations on Netflix?  They never recommend anything I’m interested in.  

I always watch shit I don't like just to fuck up their recommendations.  It's my way of sticking it to the man.  I bet Tang's algorithm can't account for that.

My wife screws up my recommendations by constantly watching shit under my profile.  My 7 year old kids are capable of switching profiles, but she just rolls with whoever.  What a bitch.  Do I need to invest in a quantum computer?

Edited by Gene Parmesan

Meh. Wake me up when he re-targets an airborne directed energy weapon to a professors house thereby popping a massive serving of popcorn while embarrassing his least favorite grad student.

4 hours ago, idigTexas said:

4?

Potato

The answer is 42.  The answer is ALWAYS 42, but then again I'm fucking old...

2 hours ago, Gene Parmesan said:

My wife screws up my recommendations by constantly watching shit under my profile.  My 7 year old kids are capable of switching profiles, but she just rolls with whoever.  What a bitch.  Do I need to invest in a quantum computer?

No but you should invest in the wives and the stupid shit they do thread.

24 minutes ago, NorthLoop said:

Don't ever let this kid get laid. He could go full Costanza. 

I have a hunch that we're safe.

3 hours ago, Bobby_Batronic said:

Meh. Wake me up when he re-targets an airborne directed energy weapon to a professors house thereby popping a massive serving of popcorn while embarrassing his least favorite grad student.

It's a laser beam bozo!

32 posts. Y'all slippin.

 

The source material is admittedly great, but post for post, this is the single greatest single page of a thread I have ever read. Outstanding. Congrats to the kid, too. 

6 minutes ago, closetojumping said:

The source material is admittedly great, but post for post, this is the single greatest single page of a thread I have ever read. Outstanding. Congrats to the kid, too. 

it was

7 hours ago, Gene Parmesan said:

My wife screws up my recommendations by constantly watching shit under my profile.  My 7 year old kids are capable of switching profiles, but she just rolls with whoever.  What a bitch.  Do I need to invest in a quantum computer?

Tell your wife you need some Tang and that you can find it on campus. 

Edited by Chuychanga


There is an "a"/"i" joke here, but I can't find it right now.

(Perhaps a classical algorithm would help.)
 

 

14 hours ago, Gene Parmesan said:

My wife screws up my recommendations by constantly watching shit under my profile.  My 7 year old kids are capable of switching profiles, but she just rolls with whoever.  What a bitch.  Do I need to invest in a quantum computer?

no, you just need to deliver her a quantum bitch-slap across the face

Edited by 52-80

15 hours ago, NeverMarryAStripper said:

I always watch shit I don't like just to fuck up their recommendations.  It's my way of sticking it to the man.  I bet Tang's algorithm can't account for that.

WILDCARD, BITCHES!

2 hours ago, Upgrayedd said:

Would be a lot cooler if his parents named him Wu 

Martin Shkreli would hire him on the spot if that was the case.

2 hours ago, Jive Turkey said:

Tang should go work for Pied Piper.

 

Richard. Hello. I went to China to do new new internet. Thank you. Enjoy your house. I love you, Tang. 

7 hours ago, Upgrayedd said:

Would be a lot cooler if his parents named him Wu 

Either that or Poon.

Edited by phdhorn

On ‎8‎/‎2‎/‎2018 at 12:42 PM, Mojo Hand said:

I hope he sent a jar of Tang to the quantum researchers he punked.  It would be a great calling card.   Tang motherfucker!

He grabs a handful of it and throws it up in the air Lebron style.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

Configure browser push notifications

Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.